HDU-3790-最短路径 - c++编程基础

题目要求先选最短的道路，如果没有最短路可选，即几条道路都相等，再考花费。用Dijkstra更快一些。在选出最短边的同时加上对应的花费就可以了。详细请看代码：

 
#include  
#include  
#include  
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]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<