A - Til the Cows Come Home

这是一道最短路的模板的，很裸的模板题可惜我还是没能1A，是因为我不知道dijkstra需要判断重复的边，dijkstra是利用邻接矩阵存的值，如果有两条相同的边重复输入且边的权值不同，那么如果靠后的那条边权值比前面的那条大，这个同一条边的较大的值会覆盖之前那个较小的值，那么我们求出的最终路径就不是最短路径；

下面贴代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std;
int t,n;
const int inf = 1e8;
int map[1010][1010];
int dist[1010];
int s[1010];

void dijkstra(int v)
{
    for(int i =1;i<=n;i++)
    {
        dist[i] = map[v][i];
        s[i] = 0;
    } 
    s[v] = 1;dist[v] = 0;
    for(int i =0;i<n-1;i++)
    {
        int min = inf,u = v;
        for(int i=1;i<=n;i++)
        {
            if(!s[i]&&dist[i]<min)
            {
                min = dist[i];
                u = i;
            }
        }
        s[u] = 1;
        for(int i = 1;i<=n;i++)
        {
            if(!s[i] && dist[u] + map[u][i]<dist[i])
            {
                dist[i] = dist[u] + map[u][i];
            }
        }
    } 
}
int main()
{
    scanf("%d%d",&t,&n);
    for(int i = 1;i<=n;i++)
    {
        for(int j =1;j<=n;j++)
        {
            if(i!=j)
            {
                map[i][j] = inf;
            }
        }
    }
    for(int i = 0;i<t;i++)
    {
        int a,b,cost;
        scanf("%d%d%d",&a,&b,&cost);
        map[a][b] = min(map[a][b],cost);
        map[b][a] = min(map[b][a],cost);
    }
    dijkstra(1);
    printf("%d\n",dist[n]);
}