QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80392#5458. Shortest Path QuerychihikTL 1ms5944kbC++141.2kb2023-02-23 16:15:112023-02-23 16:15:12

Judging History

你现在查看的是测评时间为 2023-02-23 16:15:12 的历史记录

  • [2024-06-21 12:37:44]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:2ms
  • 内存:6108kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 16:15:12]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5944kb
  • [2023-02-23 16:15:11]
  • 提交

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
...

output:


result: