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
0 / 100
4000 ms 38156 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 Incorrect 29 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 38156 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -