朴素dijstra

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 510;

//在所有最短路中，找一个花费最小的路径,并输出最短路径经过的城市,路径距离，总成本

//print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path.
//在一行中打印从起点到目的地的最短路径上的城市，然后是路径的总距离和总成本。

int n,m,S,T;
int d[N][N],c[N][N];
int dist[N],cost[N],pre[N];
bool st[N];

void dijstra()
{
    memset(dist,0x3f,sizeof dist);
    memset(cost,0x3f,sizeof cost);

    dist[S] = 0,cost[S] = 0;

    for(int i = 0; i<n; i++)
    {
        int t = -1;
        for(int j = 0; j<n; j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t = j;

        st[t] = true;

        for(int j = 0; j<n; j++)
            if(dist[j]>dist[t]+d[t][j])
            {
                dist[j] = dist[t]+d[t][j];
                cost[j] = cost[t]+c[t][j];
                pre[j] = t;//j结点前面是t
            }
            else if(dist[j]==dist[t]+d[t][j] && cost[j]>cost[t]+c[t][j])
            {
                cost[j] = cost[t] + c[t][j];
                pre[j] = t;//j结点前面是t
            }
    }
}

int main()
{
    cin>>n>>m>>S>>T;
    memset(d,0x3f,sizeof d);
    memset(c,0x3f,sizeof c);

    while(m--)
    {
        int a,b,x,y;
        cin>>a>>b>>x>>y;
        d[a][b] = d[b][a] = min(d[a][b],x);
        c[a][b] = c[b][a] = min(c[a][b],y);
    }

    dijstra();

    vector<int> path;
    for(int i = T; i!=S; i = pre[i]) path.push_back(i);
    //倒着输出
    cout<<S;
    for(int i = path.size()-1; i>=0; i--) cout<<' '<<path[i];
    cout<<' '<<dist[T]<<' '<<cost[T]<<endl;
    return 0;
}

堆优化dijstra

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int N=2000;
typedef pair<int ,int > PII;

int h[N],w[N],c[N],e[N],ne[N],idx;
int dist[N],cost[N],pre[N];     //cost记录最短路的花费  pre记录前一个结点
int n,m,s,t;
bool st[N];

void add(int a,int b,int g,int d)
{
    e[idx]=b;
    w[idx]=g,c[idx]=d;
    ne[idx]=h[a],h[a]=idx++;
}

void dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    memset(cost,0x3f,sizeof(cost));
    dist[s]=0,cost[s]=0;

    priority_queue<PII,vector<PII>,greater<PII> >heap;
    heap.push({0,s});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,dis=t.first;

        if(st[ver])continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});

                cost[j]=cost[ver]+c[i];     //更新最短距离时更新花费和路径
                pre[j]=ver;
            }
            else if(dist[j]==dis+w[i]&&cost[j]>cost[ver]+c[i])      //机理一样短且花费更小 更新花费和路径
            {
                cost[j]=cost[ver]+c[i];
                pre[j]=ver;
            }
        }
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    cin>>n>>m>>s>>t;

    while(m--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d),add(b,a,c,d);
    }
    dijkstra();

    vector<int> path;       //把路径倒着存进path里 倒着输出一遍就是正的
    for(int i=t;i!=s;i=pre[i])path.push_back(i);
    cout<<s<<" ";
    for(int i=path.size()-1;i>=0;i--)cout<<path[i]<<" ";
    cout<<dist[t]<<" "<<cost[t];
    return 0;
}