HDU-3790-最短路徑

題目要求先選最短的道路，如果沒有最短路可選，即幾條道路都相等，再考花費。用Dijkstra更快一些。在選出最短邊的同時加上對應的花費就可以了。詳細請看代碼：

 
#include<iostream>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
#define MAX 1002  
#define inf 999999  
int map[MAX][MAX],cost[MAX][MAX];  
int n;  
void DJ(int st,int en)//Dijkstra 傳入起點和終點  
{  
    int i,j,MIN,v;  
    int flag[MAX],dis[MAX],value[MAX];  
    for(i=1;i<=n;i++)  
    {  
        dis[i]=map[st][i];  
        value[i]=cost[st][i];//與一般模板相似，多加一個花費而已  
    }  
    memset(flag,0,sizeof(flag));  
    flag[st]=1;  
    for(i=1;i<=n;i++)  
    {  
        MIN=inf;  
        for(j=1;j<=n;j++)  
        {  
            if(!flag[j]&&MIN>dis[j])  
            {  
                v=j;  
                MIN=dis[j];  
            }  
        }  
        if(MIN==inf)break;  
        flag[v]=1;  
        for(j=1;j<=n;j++)  
        {  
            if(!flag[j]&&map[v][j]<inf)  
            {  
                if(dis[j]>dis[v]+map[v][j])  
                {  
                    dis[j]=dis[v]+map[v][j];  
                    value[j]=value[v]+cost[v][j];//先選好邊長，同時也把對應的花費加上  
                }  
                else  
                    if(dis[j]==dis[v]+map[v][j])//如果路長相等，則優先花費小的  
                {  
                    if(value[j]>value[v]+cost[v][j])  
                        value[j]=value[v]+cost[v][j];  
                }  
            }  
        }  
  
    }  
    cout<<dis[en]<<" "<<value[en]<<endl;//輸出到終點的最短路和花費  
}  
int main()  
{  
    int i,j,m,a,b,d,p,st,en;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        if(n==0&&m==0)break;  
        //memset(map,inf,sizeof(map));  
        //memset(cost,inf,sizeof(cost));  
        for(i=1;i<=n;i++)  
            for(j=1;j<=n;j++)//初始化為最大值，用for循環更快一些  
        {  
            map[i][j]=inf;  
            cost[i][j]=inf;  
        }  
        while(m--)  
        {  
            scanf("%d%d%d%d",&a,&b,&d,&p);  
            if(d<map[a][b]||(d==map[a][b]&&p<cost[a][b]))  
            {  
                map[a][b]=map[b][a]=d;  
                cost[a][b]=cost[b][a]=p;//開兩個二維數組分別記錄邊長和花費  
            }  
        }  
        scanf("%d%d",&st,&en);  
        DJ(st,en);  
    }  
    return 0;  
}