제출 #1140194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140194		Agageldi	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4094 ms	23908 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 200006
#define pb push_back
#define ff first
#define ss second
#define sz(s) (int)s.size()
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

ll n,dp[N], dis[N], k, t, m, q, answer, vis[N], tr;
priority_queue <pii> p;
vector <pii> v[N];

void solve(int x) {
	queue <ll> d;
	dp[x] = dis[x];
	d.push(x);
	while(!d.empty()) {
		int a = d.front();
		d.pop();
		for(auto i : v[a]) {
			if(dp[i.ff] >= min(dp[a],dis[i.ff])) continue;
			dp[i.ff] = min(dp[a],dis[i.ff]);
			d.push(i.ff);
		}
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i<=n;i++) {
		dis[i] = INT_MAX;
	}
	for(int i = 1; i <= m; i++) {
		int x, y, lentgh;
		cin >> x >> y >> lentgh;
		v[x].pb({y,lentgh});
		v[y].pb({x,lentgh});
	}
	cin >> k;
	for(int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		dis[x] = 0;
		p.push({0, x});
	}
	while(!p.empty()) {
		int val = p.top().ss;
		p.pop();
		for(auto i : v[val]) {
			if(dis[i.ff] <= dis[val] + i.ss) continue;
			dis[i.ff] = dis[val] + i.ss;
			p.push({(-1) * dis[i.ff],i.ff});
		}
	}
	cin >> q;
	for(int i = 1;i <= q; i++) {
		int x, y;
		cin >> x >> y;
		answer = 0;
		memset(dp,0,sizeof dp);
		solve(x);
		cout << dp[y] << '\n';		
	}
}
/*
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
*/

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