Dijkstra算法的应用
总是爱犯的一个错误就是在构建图的时候总是构建单个边。害,应该两个边都加进去(因为是无向图)。

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
const int maxn=1001; 
struct graph{
    int to;
    int l;
    int w;
};
struct Point{
    int index; //点的下标 
    int weight;//源点到此点的距离
    Point(int i,int w):index(i),weight(w){}
    inline bool operator < (const Point &p)const{
        return weight>p.weight;//距离近的优先级大 
    } 
};
vector<graph> g[maxn];
int dis[maxn];
int path[maxn];
int cost[maxn]; 
void init(int n){
    for(int i=0;i<=n;i++){
        dis[i]=INT_MAX;
        cost[i]=INT_MAX;
        path[i]=0;
        g[i].clear();
    }
}
void dijkstra(int s){
    priority_queue<Point> q;
    dis[s]=0;
    cost[s]=0;
    q.push(Point(s,dis[s]));
    while(!q.empty()){
        int u=q.top().index;
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int to=g[u][i].to;
            int l=g[u][i].l;
            int w=g[u][i].w;
            if(dis[to]>dis[u]+l || (dis[to]==dis[u]+l && cost[to]>cost[u]+w)){
                dis[to]=dis[u]+l;
                cost[to]=cost[u]+w;
                q.push(Point(to,dis[to]));
                path[to]=u;
            }
        }
    } 
}
int main(){
    int n,m;
    int a,b,d,p;
    int s,t;
    graph temp;
    while(cin>>n>>m){
        if(n==0&&m==0)break;
        init(n);
        for(int i=0;i<m;i++){
            cin>>a>>b>>d>>p;
            temp.to=b;
            temp.l=d;
            temp.w=p;
            g[a].push_back(temp);
            temp.to=a;
            g[b].push_back(temp);
        }
        cin>>s>>t;
        dijkstra(s);
        cout<<dis[t]<<" "<<cost[t]<<endl;
    }
    return 0;
}