-
Notifications
You must be signed in to change notification settings - Fork 0
/
1030.cpp
86 lines (85 loc) · 2.2 KB
/
1030.cpp
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//
// main.cpp
// test
//
// Created by 李寻欢 on 2019/10/1.
// Copyright © 2019 李寻欢. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string.h>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 510;
int n,m,s,d;
typedef pair<int, int> pp;
vector<pp> g[MAXN];
bool vis[MAXN] = { false };
int dis[MAXN];
int pre[MAXN];
int total[MAXN];
int cost[MAXN][MAXN];
vector<int> path;
void dfs(int s,int d){
if(d != s){
path.push_back(d);
dfs(s, pre[d]);
}
}
void Dijkstra(int s){
fill(total, total+MAXN, INF);
fill(dis, dis+MAXN, INF);
for(int i=0;i<n;++i) pre[i] = i;
dis[s] = 0;
total[s] = 0;
priority_queue<pp,vector<pp>,greater<pp>> q;
q.push({0,s});
while (q.size()) {
pp cur = q.top();
q.pop();
if(vis[cur.second]) continue;
vis[cur.second] = true;
for(int i=0;i<g[cur.second].size();++i){
int distance = g[cur.second][i].first;
int to = g[cur.second][i].second;
if(vis[to] == false && cur.first + distance < dis[to]){
dis[to] = cur.first + distance;
pre[to] = cur.second;
total[to] = total[cur.second] + cost[cur.second][to];
q.push({dis[to],to});
}else if(vis[to] == false && cur.first + distance == dis[to]){
if(total[to] > total[cur.second] + cost[cur.second][to]){
total[to] = total[cur.second] + cost[cur.second][to];
pre[to] = cur.second;
q.push({dis[to],to});
}
}
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&d);
for(int i=0;i<m;++i){
int a,b,c,distance;
scanf("%d%d%d%d",&a,&b,&distance,&c);
g[a].push_back({distance,b});
g[b].push_back({distance,a});
cost[a][b] = cost[b][a] = c;
}
Dijkstra(s);
dfs(s,d);
printf("%d ",s);
for(int i=(int)path.size()-1;i>=0;i--){
printf("%d ",path[i]);
}
printf("%d %d",dis[d],total[d]);
}