学步园

第一次的最短路，还可以吧！经过别人的提醒2A.

题目链接：点击打开链接

#include<cstdio>
#include<cstring>
using namespace std;
const int N=205;
const int INF=0xffffff;
int Map[N][N];
int n,m,dis[N];
bool vis[N];
void Init()
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    Map[i][j]=INF;
}
void dijkstra(int u)
{
    //首先得初始化.
    memset(vis,0,sizeof(vis));
    vis[u]=true;
    for(int i=0;i<n;i++)
    {
        if(i!=u) dis[i]=Map[u][i];
        else dis[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        int temp=INF,t=u;
        for(int j=0;j<n;j++)
        if(!vis[j]&&(dis[j]<temp))
        {temp=dis[j];t=j;}
//        printf("temp=%d\n",temp);
//        printf("-------------\n");
        if(t==u) break;
        vis[t]=true;
        for(int j=0;j<n;j++)
        if(!vis[j]&&Map[t][j]<INF&&dis[j]>(dis[t]+Map[t][j]))
        dis[j]=dis[t]+Map[t][j];
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        Init();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(Map[a][b]>c)
            {
                Map[a][b]=c;
                Map[b][a]=c;
            }
        }
        int u,end;
        scanf("%d%d",&u,&end);
        dijkstra(u);
        if(dis[end]==INF) printf("-1\n");
        else
        printf("%d\n",dis[end]);
    }
    return 0;
}