1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
struct Edge {
long long end;
long long cmp;
long long points;
};
long long N, M, K;
long long djikstra(long long s, vector<vector<Edge>>& graph) {
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> q;
vector<bool> visited(N);
vector<long long> dist(N);
dist[s] = 0;
q.push({ 0, s });
while (!q.empty()) {
auto c = q.top();
q.pop();
visited[c.second] = true;
for (Edge& e : graph[c.second]) {
if (visited[e.end]) continue;
long long nd = dist[c.second] + e.cmp;
if (dist[e.end] == 0 || nd > dist[e.end]) {
dist[e.end] = nd;
q.push({ nd, e.end });
}
}
}
return dist[N-1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
vector<vector<Edge>> graph(N, vector<Edge>());
for (long long i = 0; i < M; i++) {
long long k1, k2, pi, ti;
cin >> k1 >> k2 >> pi >> ti;
k1--; k2--;
graph[k1].push_back({ k2, pi - ti, pi });
graph[k2].push_back({ k1, pi - ti, pi });
}
cout << K + djikstra(0, graph);
}
|
