Submission #1498619

---

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;
ll d[110];
vector<pl> cost;
vector<edge> G[110];

void dijkstra(int s) {
	priority_queue<pl, vector<pl>, greater<pl>> q;
	fill(d, 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));
			}
		}
	}
}

ll check() {
	ll sum = d[g],num = 0;
	ll temp = sum;
	ll ans=0,res=0;

	for (int j = 0; j < k-1; j++) {
		if (sum >= cost[k - 1].first) {
			ans += cost[k - 1].second;
		}
		else {
			if (j + 1 < k && sum <= cost[j + 1].first - 1 &&
				sum >= cost[j].first) {
				ans += cost[j].second;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		res = 0;
		num += d[i];
		sum -= d[i];
		for (int j = 0; j < k-1; j++) {
			if (num >= cost[k - 1].first) {
				res += cost[k - 1].second;
			}
			else {
				if (j + 1 < k && num <= cost[j + 1].first - 1 &&
					num >= cost[j].first) {
					res += cost[j].second;
				}
			}
			if (sum >= cost[k - 1].first) {
				res += cost[k - 1].second;
			}
			else {
				if (j + 1 < k && sum <= cost[j + 1].first - 1 &&
					sum >= cost[j].first) {
					res += cost[j].second;
				}
			}
		}
		ans = min(ans, res);
	}
	return ans;
}

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

	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].first >> cost[i].second;
	
	dijkstra(s);
	cout << check() << endl;
	return	0; 
}

Submission Info

Judge Result