知识点:最短路径
这个最短路径除了距离还有一个标尺,用的是dijkstra+dfs的写法,一开始用的是邻接表,但是发现dfs的时候写不下去了,就又换成了邻接矩阵,这个东西以后要解决的,
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int N = 505;
const int INF = 0x7fffffff;
int n, m, c1, c2, tot, min_cost = INF;
int edge[N][N], cost[N][N];
int dist[N], vis[N];
vi pre[N], tmp, ans;
void dijkstra() {
fill(dist, dist + N, INF);
dist[c1] = 0;
for (int i = 0; i < n; i++) {
int u = -1, Min = INF;
for (int j = 0; j < n; j++) {
if (!vis[j] && dist[j] < Min) { Min = dist[j]; u = j; }
}
if (u == -1) return;
vis[u] = 1;
for (int j = 0; j < n; j++) {
if (!edge[u][j] || vis[j]) continue;
if (dist[j] > dist[u] + edge[u][j]) {
dist[j] = dist[u] + edge[u][j];
pre[j].clear(); pre[j].pb(u);
} else if (dist[j] == dist[u] + edge[u][j]) {
pre[j].pb(u);
}
}
}
}
void dfs(int s, int e) {
if (s == e) {
tmp.pb(s);
int num = 0;
for (int i = sz(tmp) - 1; i >= 1; i--) {
num += cost[tmp[i]][tmp[i - 1]];
}
if (num < min_cost) {
min_cost = num;
ans = tmp;
}
tmp.pop_back();
return;
}
tmp.pb(e);
for (int i = 0; i < sz(pre[e]); i++) dfs(s, pre[e][i]);
tmp.pop_back();
}
int main() {
cin >> n >> m >> c1 >> c2;
for (int i = 0; i < m; i++) {
int x, y, z, w; cin >> x >> y >> z >> w;
edge[x][y] = edge[y][x] = z;
cost[x][y] = cost[y][x] = w;
}
dijkstra();
dfs(c1, c2);
for (int i = sz(ans) - 1; i >= 0; i--) cout << ans[i] << " ";
cout << dist[c2] << " " << min_cost;
return 0;
}