Submission #671643

#	Time	Username	Problem	Language	Result	Execution time	Memory
671643		smartmonky	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4070 ms	35252 KiB

plan

#include <bits/stdc++.h>
  
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
 
const int N = 1e5 + 10;
int d[N];
vector < pair <int,int> > g[N];
int n;
int dji(int f, int s){
	vector <int> dist(n + 1, -1e9);
	set <pair <int,int> > st;
	st.insert({0, f});
	dist[f] = d[f];
	while (!st.empty()) {
		int v = (--st.end())->second;
		st.erase (--st.end());
		for (size_t j=0; j< g[v].size(); ++j) {
			int to = g[v][j].first;
			if (min(dist[v], d[to]) > dist[to]) {
				st.erase (make_pair (d[to], to));
				if(to == s){
					return  min(dist[v], d[to]);
				}
				dist[to] = min(dist[v], d[to]);
				st.insert (make_pair (d[to], to));
			}
		}
	}
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d, 0x3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	int k;
	cin >> k;
	set <pair <int,int> > st;
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		st.insert({0, a});
		d[a] = 0;
	}
	while (!st.empty()) {
		int v = st.begin()->second;
		st.erase (st.begin());
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				st.insert (make_pair (d[to], to));
			}
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a, b;
		cin >> a >> b;
		cout << dji(a,b) << endl;
	}
}

Compilation message (stderr)

plan.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
plan.cpp: In function 'long long int dji(long long int, long long int)':
plan.cpp:16:31: warning: control reaches end of non-void function [-Wreturn-type]
   16 |  vector <int> dist(n + 1, -1e9);
      |                               ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46