概述

，，，尽量不看以前的代码打出来，，，熟悉一下dijkstra的格式和链式前向星的写法，，，，

虽然是水题，，，但是一开始没考虑取费用最短的wa了一发，，，，QAQ

分析

链式前向星存图，，再加一个数组保存源点到每个点的费用cst[maxm]，，，注意取最少的费用

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 1e3 + 10;const int maxm = 1e5 + 10;const int inf = 0x3f3f3f3f;int head[maxm << 1];bool vis[maxn];int dis[maxm];int cst[maxm];int cnt;int n , m;struct edge{    int to;    int w;    int c;    int last;}edge[maxm << 1];void addedge(int u , int v , int w , int c){    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].c = c;    edge[cnt].last = head[u];    head[u] = cnt++;}struct node{    int u;    int w;    node(int _u , int _w):u(_u) , w(_w){}    bool operator < (const node &res) const    {        return w > res.w;    }};void dijkstra(int n , int s){    for(int i = 1; i <= n; ++i)        dis[i] = (i == s) ? 0 : inf;    memset(cst , inf , sizeof cst);cst[s] = 0;    memset(vis , false , sizeof vis);    priority_queue
         
           q; while(!q.empty()) q.pop(); q.push(node(s , 0)); while(!q.empty()) { node x = q.top();q.pop(); int u = x.u; if(vis[u]) continue; vis[u] = true; for(int i = head[u] ; ~i; i = edge[i].last) { int to = edge[i].to; int w = edge[i].w; int c = edge[i].c; if(!vis[to] && dis[u] + w <= dis[to]) { dis[to] = dis[u] + w; //if(cst[u] + c < cst[to]) cst[to] = cst[u] + c; q.push(node(to , dis[to])); } } }}int main(){ while(scanf("%d%d" , &n , &m) && n && m) { cnt = 0; memset(head , -1 , sizeof head); int u , v , w , c; for(int i = 1; i <= m; ++i) { scanf("%d%d%d%d" , &u , &v , &w , &c); addedge(u , v , w , c); addedge(v , u , w , c); } int s , t; scanf("%d%d" , &s , &t); dijkstra(n , s); printf("%d %d\n" , dis[t] , cst[t]); }}//最短路相等时注意取费用最短的////5 7//1 2 5 5//2 3 4 5//1 3 4 6//3 4 2 2//3 5 4 7//4 5 2 4//1 3 4 4//1 5//8 10