2016HUAS_ACM暑假集训3C

单源最短路径，首先想到的是Dijkstra。Dijkstra算法的思路就不啰嗦了，概括起来就是时刻保持当前节点到目标节点的距离最短。

题目大意（不进行翻译解释了，就抽离为图来表达）：有N个顶点和T条边的无向图,求从1号顶点到N号顶点的最短距离是多少。

Sample Input：（先T后N！先T后N！先T后N！）

5 5

1 2 20                //分别是两个顶点v1、v2，以及它们之间的权值 

2 3 30

3 4 20

4 5 20

1 5 100

Sample Output：

90

由于比较简单，所以也不需要太多注释。

#include<iostream>
#include<cstdio>
#include<cstring>
#define size 1001
#define INF 0x3f3f3f3f
using namespace std;
int N,T,a,b,c,i,j,k;
int land[size][size],dis[size],flag[size];

int min(int a,int b)//树的维护那里可以用判断语句，也可以用这个来选出较小的那个
{
    return ((a)<(b))?(a):(b);
}

void init()//初始化
{
    memset(land,INF,sizeof(land));
    memset(dis,INF,sizeof(dis));
    memset(flag,0,sizeof(flag));
}

void Dijkstra()
{
    dis[1]=0;
    for(i=1;i<N;i++)//遍历
    {
        int M=INF,X;
        for(j=1;j<=N;j++)
        {
            if(!flag[j]&&dis[j]<M)
            {
                M=dis[j];
                X=j;
            }
        }
        flag[X]=1;//标记
        for(k=1;k<=N;k++)//维护
            dis[k]=min(dis[k],dis[X]+land[X][k]);
    }
    cout<<dis[N]<<endl;
}

int main()
{
    while(cin>>T>>N)
    {
        init();
        while(T--)
        {
            cin>>a>>b>>c;
            if(land[a][b]>c)//只记录最短的
                land[a][b]=land[b][a]=c;
        }
        Dijkstra();
    }
    return 0;
}