POJ-2387-Til the Cows Come Home

链接：https://vjudge.net/problem/POJ-2387

题意：

给T,N。有N个点，T条路径。

T条路以L R V给出。（无向图，太久没写导致WA了一发）。

求1-N的最短路。

直接Dijkstra解决。

代码：

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
const int MAXN = 1000+10;
int Map[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];

int main()
{
    int t,n;
    int l,r,v;
    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] = 0;
            else
                Map[i][j] = 99999;
    for (int i = 0;i<t;i++)
    {
        scanf("%d%d%d",&l,&r,&v);
        if (Map[l][r] != 0)
            Map[r][l] = Map[l][r] = min(Map[l][r],v);
        else
            Map[r][l] = Map[l][r] = v;
    }
    dis[1] = 0;
    for (int i = 2;i<=n;i++)
    {
        if (Map[1][i] != 0)
            dis[i] = Map[1][i];
        else
            dis[i] = 99999;
    }
    vis[1] = 1;
    for (int i = 1;i<=n;i++)
    {
        int big = 99999;
        int w;
        for (int i = 2;i<=n;i++)
        {
            if (dis[i] < big&&vis[i] == 0)
            {
                big = dis[i];
                w = i;
            }
        }
        vis[w] = 1;
        if (w == n)
            break;
        for (int i = 1;i<=n;i++)
        {
            if (dis[i] > dis[w] + Map[w][i])
                dis[i] = dis[w] + Map[w][i];
        }
    }
    printf("%d
",dis[n]);
}