Problem Description

某省自从实行了非常多年的畅通project计划后，最终修建了非常多路。只是路多了也不好。每次要从一个城镇到还有一个城镇时，都有很多种道路方案能够选择，而某些方案要比还有一些方案行走的距离要短非常多。这让行人非常困扰。

如今。已知起点和终点，请你计算出要从起点到终点，最短须要行走多少距离。

 

Input

本题目包括多组数据，请处理到文件结束。 每组数据第一行包括两个正整数N和M(0<N<200,0<M<1000)。分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。 接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。 再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。

 

Output

对于每组数据。请在一行里输出最短须要行走的距离。

假设不存在从S到T的路线，就输出-1.

 

Sample Input

 

 

Sample Output

 

 dijsktra：

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

#define inf 0x3f3f3f3f

int n,m,a,b,x,s,t;

int map[205][205];//邻接矩阵存图；

bool vis[205];//标记是否被訪问过

int dis[205];//存每一个点距源点的距离

void dijkstra(int s)

{

    for(int i=0;i<n;i++)

    {

        dis[i]=map[s][i];

        vis[i]=false;

    }

    dis[s]=0;

    vis[s]=true;

    int pos,min;

    for(int i=1;i<n;i++)

    {

        min=inf;

        for(int j=0;j<n;j++)

        {

            if(!vis[j]&&dis[j]<min)

            {

                min=dis[j];

                pos=j;

            }

        }

        vis[pos]=true;

        for(int j=0;j<n;j++)

        {

            if(!vis[j]&&dis[j]>dis[pos]+map[pos][j])

                dis[j]=dis[pos]+map[pos][j];

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=0;i<n;i++)

           for(int j=0;j<n;j++)

          {

              map[i][j]=map[j][i]=inf;

          }

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d",&a,&b,&x);

            if(map[a][b]>x)          //假设有重边！

！。！

            map[a][b]=map[b][a]=x;

        }

        scanf("%d%d",&s,&t);

        dijkstra(s);

        if(dis[t]==inf)

            printf("-1\n");

        else

            printf("%d\n",dis[t]);

    }

    return 0;

}

floyd：

#include<stdio.h>

#include<iostream>

using namespace std;

#define inf 0x3f3f3f3f

int n,m,a,b,x,s,t;

int map[205][205];

void floyd()

{

    for(int k=0;k<n;k++)

        for(int i=0;i<n;i++)

           for(int j=0;j<n;j++)

    {

        if(map[i][k]+map[k][j]<map[i][j])

            map[i][j]=map[i][k]+map[k][j];

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)

            map[i][j]=(i==j?0:inf);

        for(int i=0;i<m;i++)

           {

               scanf("%d%d%d",&a,&b,&x);

               if(map[a][b]>x)

                  map[a][b]=map[b][a]=x;

           }

           scanf("%d%d",&s,&t);

           floyd();

        if(map[s][t]==inf)

            printf("-1\n");

        else printf("%d\n",map[s][t]);

    }

    return 0;

}