Dijkstra算法（优先队列优化）

  • 结构体 增加 花费项（cost）
  • 增加 更新规则（同距离时选花费更少的）
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<climits>
using namespace std;

const int maxn=100001;
const int INF=INT_MAX;

struct Point{//优先队列的结点（编号、到源点的距离及花费）
    int next;
    int distance;
    int cost; 
    bool operator <(Point x)const{
        if(distance==x.distance)return cost>x.cost;
        else return distance>x.distance;
    }
    Point(int n,int d,int c):next(n),distance(d),cost(c){}
    Point(){}
};

struct Edge{//图的边
    int to;
    int distance;
    int cost;
    Edge(int t,int d,int c):to(t),distance(d),cost(c){}
    Edge(){}
};

vector<Edge>graph[maxn];//图的邻接矩阵
int dis[maxn];
int cos[maxn];

void Dijkstra(int start,int n){
    fill(dis+1,dis+n+1,INF);
    fill(cos+1,cos+n+1,INF);
    dis[start]=0;
    cos[start]=0;
    
    priority_queue<Point>myqueue;
    myqueue.push(Point(start,0,0));
    while(!myqueue.empty()){
        int u=myqueue.top().next;//根据新选的u来更新距离
        myqueue.pop();
        for(int i=0;i<graph[u].size();i++){
            int x=graph[u][i].to;
            int y=graph[u][i].distance;
            int z=graph[u][i].cost;
            if((dis[u]+y<dis[x])||(dis[u]+y==dis[x]&&cos[u]+z<cos[x])){
                dis[x]=dis[u]+y;
                cos[x]=cos[u]+z;
                myqueue.push(Point(x,dis[x],cos[x]));
            }
        }
    }
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)break;
        memset(graph,0,sizeof(graph));
        for(int i=0;i<m;i++){
            int f,t,d,c;
            scanf("%d%d%d%d",&f,&t,&d,&c);
            graph[f].push_back(Edge(t,d,c));//无向边
            graph[t].push_back(Edge(f,d,c));
        }
        int start,terminal;
        scanf("%d%d",&start,&terminal);
        Dijkstra(start,n);
        printf("%d %d\n",dis[terminal],cos[terminal]);
    }
    
    return 0;
}