题解 | #最短路径问题#

dijkstra算法（其实感觉不太是原始的那种算法，而是一种代码更短的模拟dijkstra算法）。由于使用了优先队列，所以时间复杂度也从V^2变成了ElogV

#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;

const int MAXN=1001;
const int INF=2000000000;

struct edge{
    int to;
    int length;
    int money;
    edge(int t,int l,int m):to(t),length(l),money(m){}
};

struct point{
    int number;
    int distance;
    point(int n,int d):number(n),distance(d){}
    bool operator<(const point&p)const{
        return distance>p.distance;
    }
};

vector<edge>graph[MAXN];
int dis[MAXN];
int money[MAXN];

void dijkstra(int s){
    priority_queue<point>pq;
    dis[s]=0;
    money[s]=0;
    pq.push(point(s,dis[s]));
    while(!pq.empty()){
        int u=pq.top().number;
        pq.pop();
        for(int i=0;i<graph[u].size();++i){
            int v=graph[u][i].to;
            int l=graph[u][i].length;
            int p=graph[u][i].money;
            if(dis[v]>dis[u]+l||(dis[v]==dis[u]+l&&money[v]>money[u]+p)){
                dis[v]=dis[u]+l;
                money[v]=money[u]+p;
                pq.push(point(v,dis[v]));
            }
        }
    }
    return;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        memset(graph,0,sizeof(graph));
        fill(dis,dis+n+1,INF);
        fill(money,money+n+1,INF);
        while(m--){
            int from,to,length,money;
            cin>>from>>to>>length>>money;
            graph[from].push_back(edge(to,length,money));
            graph[to].push_back(edge(from,length,money));
        }
        int s,t;
        cin>>s>>t;
        dijkstra(s);
        cout<<dis[t]<<" "<<money[t]<<endl;
    }
    return 0;
}