最短路

单源最短路dij

#include <iostream>
#include <memory.h>
#include <bits/stdc++.h>
using namespace std;
const int IN = (1<<28);
int N,M,S,T;
int G[1005][1005];
int dist[1005];
int visited[1005];
void dij()
{
    memset(dist, 0, sizeof(dist));
    for( int i = 1; i <= N; i++ )
        dist[i] = G[1][i];
    memset(visited, 0, sizeof(visited));
    visited[1] = 0;
    while(1)
    {
        int Min = IN, Minv = 0;
        for( int i = 1; i <= N; i++ )
        {
            if( !visited[i] && dist[i] < Min )
            {
                Minv = i;
                Min = dist[i];
            }
        }
        if( !Minv )
            break;
        else
        {
            visited[Minv] = 1;
            for(int i = 1; i <= N; i++ )
            {
                if( !visited[i] && dist[i] > dist[Minv] + G[Minv][i] )
                {
                    dist[i] = dist[Minv] + G[Minv][i];
                }
            }
        }
    }
}
int main()
{
    while(cin >> N >> M, N!=0)
    {
    for( int i = 1; i <= N; i++ )
        for( int j = 1; j <= N; j++ )
        {
            if( i==j )
                G[i][j] = 0;
            else
                G[i][j] = IN;
        }
    while( M-- )
    {
        int Start,End,Length;
        cin >> Start >> End >> Length;
        G[Start][End] = Length;
        G[End][Start] = Length;
    }
    dij();
    cout << dist[N] << endl;
    }
    return 0;
}