2544.cpp

HDOJ2501-2681acm解题报告

#include <iostream>
//#include <algorithm>
using namespace std;
int main()
{
    int x,y,n,m,i,j,d,s,t,map[201][201],dis[201];//dis记录最短路径
    bool visited[201];//map记录图信息
    while(cin>>n>>m && n && m)
    {
        for(i = 0;i<n;i++)//初始化
        {
            for(j = 0;j<n;j++)
            {
                map[i][j] = 0;
            }
            dis[i] = INT_MAX;
            visited[i] = false;
        }
        for(i = 0;i<m;i++)	//输入图信息
        {
            cin>>x>>y>>d;
            if(map[x-1][y-1] == 0||map[x-1][y-1]>d)	//与前不同!!!
                map[x-1][y-1] = map[y-1][x-1] = d;
        }

        s=0; t=n-1;//s为起点  t为终点
        dis[s] = 0;
        while(1)
        {
            d = INT_MAX;
            for(i = 0;i<n;i++)	//找到下一个最短路径长为d，顶点为j
            {
                if(!visited[i]&&dis[i]<d)
                {
                    d = dis[i];
                    j = i;
                }
            }
            if(d == INT_MAX)//无路
                break;
            visited[j] = true;
            for(i = 0;i<n;i++)//更新所有与j连接的路径表
            {
                if(!visited[i]&&map[i][j]&&dis[i]>map[i][j]+dis[j])
                    dis[i] = dis[j] + map[i][j];
            }
        }
        if(visited[t])
            cout<<dis[t]<<endl;
        else
            cout<<"-1"<<endl;
    }
    return 0;
}