题目描述

C++代码

样例

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<unordered_set>
#include<climits>
using namespace std;
const int N = 520;
int n, m, d, s;
int mincost1 = 1e9;
int minds = 1e9;
vector<int> path;
int vis[N];
int pre[N];
struct edge {
    int ne;
    int cost;
    int dis;
};
vector<edge> vc[N];
void dfs(int u)
{
    int disorder[N];
    int mincost[N];
    memset(disorder, 0x3f, sizeof disorder);
    memset(mincost, 0x3f, sizeof mincost);
    memset(pre, -1, sizeof pre);
    disorder[u] = 0;
    mincost[u] = 0;
    for (int i = 0; i < n; i++)
    {
        int uj = n;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && disorder[j] < disorder[uj])
            {
                uj = j;
            }
        }
        if (uj == n) {
            return;
        }
        vis[uj] = 1;
        for (auto& t : vc[uj])
        {
            int ne = t.ne;
            int dis = t.dis;
            int cost = t.cost;
            if (disorder[ne] == (disorder[uj] + dis))
            {
                if (mincost[ne] > (mincost[uj] + cost))
                {
                    pre[ne] = uj;
                    mincost[ne] = (mincost[uj] + cost);
                }
            }
            else {
                if (disorder[ne] > (disorder[uj] + dis))
                {
                    disorder[ne] = (disorder[uj] + dis);
                    mincost[ne] = (mincost[uj] + cost);
                    pre[ne] = uj;
                }
            }
        }
    }
    minds = disorder[d];
    mincost1 = mincost[d];
}
int main()
{
    memset(vis, false, sizeof vis);
    cin >> n >> m >> s >> d;
    while (m--)
    {
        int a, b, c, d1;
        cin >> a >> b >> c >> d1;
        edge e;
        e.ne = b;
        e.dis = c;
        e.cost = d1;
        vc[a].push_back(e);
        edge e1;
        e1.ne = a;
        e1.dis = c;
        e1.cost = d1;
        vc[b].push_back(e1);
    }
    dfs(s);
    for (int i = d; i != -1; i = pre[i])
    {
        path.push_back(i);
    }
    reverse(path.begin(), path.end());
    cout << path[0];
    for (int i = 1; i < path.size(); i++)
    {
        cout << " " << path[i];
    }
    cout << " " << minds << " " << mincost1;
    return 0;
}