QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80392 | #5458. Shortest Path Query | chihik | TL | 1ms | 5944kb | C++14 | 1.2kb | 2023-02-23 16:15:11 | 2023-02-23 16:15:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pii pair< int , int >
#define fi first
#define sc second
#define mp make_pair
pii operator + ( pii a , pii b ) { return mp( a.fi + b.fi , a.sc + b.sc ); }
const int MAXN = 5e4;
int n , m , q;
struct Edge { int v; pii w; };
vector< Edge > Graph[ MAXN + 5 ];
vector< pii > t[ MAXN + 5 ];
int main( ) {
// freopen("gray.in","r",stdin);
// freopen("gray.out","w",stdout);
scanf("%d %d",&n,&m);
for( int i = 1 , u , v , w ; i <= m ; i ++ ) {
scanf("%d %d %d",&u,&v,&w);
Graph[ u ].push_back( { v , w ? mp( 0 , 1 ) : mp( 1 , 0 ) } );
}
t[ 1 ].push_back( mp( 0 , 0 ) );
for( int u = 1 ; u <= n ; u ++ ) {
sort( t[ u ].begin() , t[ u ].end() );
vector< pii > tmp;
for( pii du : t[ u ] )
if( tmp.empty() || du.fi != tmp.back().fi ) tmp.push_back( du );
t[ u ] = tmp;
for( Edge v : Graph[ u ] ) for( pii du : t[ u ] )
t[ v.v ].push_back( du + v.w );
}
scanf("%d",&q);
for( int i = 1 , a , b , s ; i <= q ; i ++ ) {
scanf("%d %d %d",&a,&b,&s);
int ans = 1e9;
for( pii v : t[ s ] ) ans = min( ans , a * v.fi + b * v.sc );
printf("%d\n", ans );
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5944kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...