Submission #1498678

---

Source Code Expand

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

struct edge {
	int cost;
	int to;
};

ll n, m, k,s,g;
ll INF = 1000000000;
vector<pl> cost;
vector<edge> G[60010];
vector<ll> ds, dg;

vector<ll> dijkstra(int s) {
	priority_queue<pl, vector<pl>, greater<pl>> q;
	vector<ll> d(n,INF);
	d[s] = 0;
	q.push(pl(0, s));

	while (!q.empty()) {
		pl p = q.top(); q.pop();
		int v = p.second;
		if (d[v] < p.first)continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				q.push(pl(d[e.to], e.to));
			}
		}
	}
	return d;
}

ll check() {
	ll ans = INF;
	for (int i = 0; i < n; i++) {
		ll res = 0;
		for (int j = 0; j < k; j++) {
			if (cost[j].first <= ds[i] && cost[j+1].first > ds[i])
				res += cost[j].second;
			if (cost[j].first <= dg[i] && cost[j+1].first > dg[i])
				res += cost[j].second;
		}
		if (cost[k].first <= ds[i])res += cost[k].second;
		if (cost[k].first <= dg[i])res += cost[k].second;
		ans = min(ans, res);
	}
	return ans;
}

int main()
{
	cin >> n >> m >> k >> s >> g;
	cost.resize(k+1);

	for (int i = 0; i < m; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		G[a].push_back({d,b});
		G[b].push_back({d,a });
	}

	for (int i = 0; i < k; i++)
		cin >> cost[i+1].first >> cost[i+1].second;
	
	ds = dijkstra(s);
	dg = dijkstra(g);
	cout << check() << endl;
	return	0; 
}

Submission Info

Judge Result