Submission #166606

# Submission time Handle Problem Language Result Execution time Memory
166606 2019-12-03T04:25:56 Z abil Evacuation plan (IZhO18_plan) C++14
10 / 100
4000 ms 34888 KB
#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

vector<pair<int,int >> g[N];
int dist[N];

main()
{
	int n, k, m, v, u, w;
	cin >> n >> m;
	for(int i = 1;i <= m; i++){
		scanf("%d%d%d", &v, &u, &w);
		g[v].pb({u, w});
		g[u].pb({v, w});
	}
	memset(dist,0x3f3f3f3f,sizeof(dist));
	cin >> k;
	priority_queue<pair<int,int > > q;
	for(int i = 1;i <= k; i++){
		scanf("%d", &v);
		dist[v] = 0;
		q.push({0, v});
	}
	while(!q.empty()){
		auto x = q.top();
		q.pop();
		for(auto to : g[x.sc]){
			if(dist[to.fr] >= dist[x.sc] + to.sc){
				q.push({dist[x.sc] + to.sc, to.fr});
				dist[to.fr] = dist[x.sc] + to.sc;
			}
		}
	}
	int que;
	cin >> que;
	while(que--){
		scanf("%d%d", &v, &u);
		printf("%d\n", min(dist[v], dist[u]));
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message

plan.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v, &u, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v);
   ~~~~~^~~~~~~~~~
plan.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 27 ms 27768 KB Output is correct
2 Correct 28 ms 27768 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 28 ms 27640 KB Output is correct
5 Correct 29 ms 27768 KB Output is correct
6 Correct 28 ms 27764 KB Output is correct
7 Correct 27 ms 27768 KB Output is correct
8 Correct 27 ms 27640 KB Output is correct
9 Correct 28 ms 27768 KB Output is correct
10 Correct 28 ms 27768 KB Output is correct
11 Correct 28 ms 27768 KB Output is correct
12 Correct 28 ms 27768 KB Output is correct
13 Correct 29 ms 27768 KB Output is correct
14 Correct 27 ms 27756 KB Output is correct
15 Correct 27 ms 27768 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 27 ms 27768 KB Output is correct
2 Correct 28 ms 27768 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 28 ms 27640 KB Output is correct
5 Correct 29 ms 27768 KB Output is correct
6 Correct 28 ms 27764 KB Output is correct
7 Correct 27 ms 27768 KB Output is correct
8 Correct 27 ms 27640 KB Output is correct
9 Correct 28 ms 27768 KB Output is correct
10 Correct 28 ms 27768 KB Output is correct
11 Correct 28 ms 27768 KB Output is correct
12 Correct 28 ms 27768 KB Output is correct
13 Correct 29 ms 27768 KB Output is correct
14 Correct 27 ms 27756 KB Output is correct
15 Correct 27 ms 27768 KB Output is correct
16 Execution timed out 4097 ms 31684 KB Time limit exceeded
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 4082 ms 34888 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 27 ms 27768 KB Output is correct
2 Correct 28 ms 27768 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 28 ms 27640 KB Output is correct
5 Correct 29 ms 27768 KB Output is correct
6 Correct 28 ms 27764 KB Output is correct
7 Correct 27 ms 27768 KB Output is correct
8 Correct 27 ms 27640 KB Output is correct
9 Correct 28 ms 27768 KB Output is correct
10 Correct 28 ms 27768 KB Output is correct
11 Correct 28 ms 27768 KB Output is correct
12 Correct 28 ms 27768 KB Output is correct
13 Correct 29 ms 27768 KB Output is correct
14 Correct 27 ms 27756 KB Output is correct
15 Correct 27 ms 27768 KB Output is correct
16 Execution timed out 4097 ms 31684 KB Time limit exceeded
17 Halted 0 ms 0 KB -