1030 Travel Plan (30 分)

知识点：最短路径

这个最短路径除了距离还有一个标尺，用的是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;
}