题解 | 最短路径问题

双向边，M之前只给了100010，最后一个用例数组不够存了，M设为200010，就行了

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;

typedef long long LL;
const int N=1010,M=200010,INF=0x3f3f3f3f;
typedef pair<pair<LL,LL>,LL> PIII;

long long e[M],ne[M],h[N],w[M],p[M],idx;
long long n,m;
long long dist[N];
long long expend[N];
LL s,t;
bool st[N];

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

void Dijkstra(){
    memset(st,false,sizeof(st));
    memset(dist,INF,sizeof(dist));
    memset(expend,INF,sizeof(expend));
    priority_queue<PIII,vector<PIII>,greater<PIII>> q;
    q.push({{0,0},s});
    dist[s]=0;
    expend[s]=0;

    while(q.size()){
        PIII k=q.top();
        q.pop(); 

        LL dt=k.x.x,ep=k.x.y,ver=k.y;
        if(st[ver])continue;
        st[ver]=true;

        for(LL j=h[ver];j!=-1;j=ne[j]){
            int b=e[j],c=w[j],d=p[j];

            if(st[b])continue;
            if(dist[b]>dt+c){
                dist[b]=dt+c;
                expend[b]=ep+d;
                q.push({{dist[b],expend[b]},b});
            }else if(dist[b]==dt+c){
                if(expend[b]>ep+d){
                    expend[b]=ep+d;
                    q.push({{dist[b],expend[b]},b});
                }
            }
        }
    }
}

int main(){
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        memset(h,-1,sizeof(h));
        idx=0;

        LL a,b,c,d;
        for(LL i=0;i<m;i++){
            cin>>a>>b>>c>>d;
            addb(a,b,c,d);
            addb(b,a,c,d);
        }

        cin>>s>>t;
        
        Dijkstra();

        cout<<dist[t]<<' '<<expend[t]<<endl;
    }

    return 0;
}