国际大学生程序设计竞赛例题_5.6最难的任务

1,题意:实质求顶点1到n的最短路径.
注意:有重边的可能,选择最小权值
2,解决:dijkstra算法.
3,实现代码:

#include <iostream>
using namespace std;

const int hashCnt=6000;
const int maxN=201;
const int inf=1000000;
int graph[maxN][maxN]; //无向图
int dis[maxN];//距离矩阵 到顶点的距离
bool use[maxN];//标志点是否处理


int cnt; //测试数目
int vNum;//顶点数
int eNum;//边数

void dijk(int s)
{
    for(int i=0;i<vNum;i++)
    {
        dis[i]=inf;
        use[i]=false;
    }
    int u,temp;
    while(1)
    {
        temp=inf;
        dis[s]=0;
        for(int i=0;i<vNum;i++)
        {
            if(!use[i]&&dis[i]<temp)
            {
                temp=dis[i];
                u=i;
            }
        }
        if(temp==inf) break;
        use[u]=true;
        for(int i=0;i<vNum;i++)
        {
            if( !use[i] && graph[u][i]!=-1 && dis[i]>dis[u]+graph[u][i] )
                dis[i]=dis[u]+graph[u][i];
        }
    }
}

int main()
{
    freopen("5.6.in","r",stdin);
    int x,y,d;
    cin>>cnt;
    while(cnt--)
    {
        memset(graph,-1,sizeof(graph));
        cin>>vNum>>eNum;
        while(eNum--)
        {
            cin>>x>>y>>d;
            x--,y--;
            if(graph[x][y]==-1||graph[x][y]>d)
                graph[x][y]=graph[y][x]=d;
        }
        dijk(0);
        if(dis[vNum-1]==inf) cout<<"-1"<<endl;
        else cout<<dis[vNum-1]<<endl;
    }
    return 0;
}