使用了優(yōu)先隊列+DIJSTRA實現(xiàn)

#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
const int maxn = 510;
struct node {
    node(int a, int b, int c) { v = a, len = b, w = c; }
    int v, len, w;
};
int dis[maxn], pre[maxn], cost[maxn], INF = 0x3fffffff, s;//s是源頭
bool vis[maxn];
using namespace std;
vector<node> edge[maxn];
void DFS(int a) {
    if (a != s) DFS(pre[a]);
    printf("%d ", a);
}
int main() {
    int n, m, d; scanf("%d %d %d %d", &n, &m, &s, &d);
    for (int i = 0; i < m; i++) {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        edge[a].push_back(node(b, c, d));
        edge[b].push_back(node(a, c, d));
        cost[i] = INF, dis[i] = INF;
    }
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(pair<int, int>(0, s)); cost[s] = 0; dis[s] = 0;
    for (int i = 0; i < n; i++) {
        pair<int, int> temp = q.top(); q.pop();
        int u = temp.second; vis[u] = true;
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].v;
            if (!vis[v]) {
                int len = edge[u][i].len;
                if (dis[v] > dis[u] + len) {
                    dis[v] = dis[u] + len;
                    cost[v] = cost[u] + edge[u][i].w;
                    pre[v] = u;
                    q.push(pair<int,int>(dis[v], v));
                }
                else if (dis[v] == dis[u] + len && cost[v] > cost[u] + edge[u][i].w) {
                    cost[v] = cost[u] + edge[u][i].w;
                    pre[v] = u;
                }
            }
        }
    }
    pre[s] = s;
    DFS(d);
    printf("%d %d", dis[d], cost[d]);
}

使用 DIJSTTRA+ 鄰接矩陣+DFS實現(xiàn)

#include<cstdio>//使用最原始最發(fā)雜的算法
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 510, INF = 0x3fffffff;
int edge[maxn][maxn], cost[maxn][maxn], dis[maxn], tempcost, n, s, finalcost = INF;//S是路徑的源頭
bool vis[maxn];
vector<int> pre[maxn], ans, temp;
void Dijstra(int s) {
    dis[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && dis[j] < MIN) {
                u = j;
                MIN = dis[j];
            }
        }
        if (u == -1) break;//說明已經(jīng)沒有點跟他鄰接了
        vis[u] = true;
        for (int j = 0; j < n; j++) {
            if (edge[u][j] != INF && !vis[j]) {
                if (dis[u] + edge[u][j] < dis[j]) {
                    dis[j] = dis[u] + edge[u][j];
                    pre[j].clear();
                    pre[j].push_back(u);
                }
                else if (dis[u] + edge[u][j] == dis[j])
                    pre[j].push_back(u);
            }
        }
    }
}
void DFS(int d) {
    if (d == s) {
        temp.push_back(s);
        if (tempcost < finalcost) {
            finalcost = tempcost;
            ans = temp;
        }
        temp.pop_back();
        return;
    }
    temp.push_back(d);
    for (int i = 0; i < pre[d].size(); i++) {
        tempcost += cost[d][pre[d][i]];
        DFS(pre[d][i]);
        tempcost -= cost[d][pre[d][i]];
    }
    temp.pop_back();
}
int main() {
    fill(edge[0], edge[0] + maxn * maxn, INF);
    fill(cost[0], cost[0] + maxn * maxn, INF);
    fill(dis, dis + maxn, INF);
    int m, d; scanf("%d %d %d %d", &n, &m, &s, &d);
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        scanf("%d %d", &edge[a][b], &cost[a][b]);
        edge[b][a] = edge[a][b]; cost[b][a] = cost[a][b];
    }
    Dijstra(s);
    DFS(d);
    for (int i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
    printf("%d %d", dis[d], finalcost);
}