学步园

题意：一个农场有n(1 ~ 1000)个landmarks，有t(1 ~
2000)条道路连接，问Bessie要从编号为n的landmarks到编号为1的landmarks，最少得走多少的路程？

思路：dijkstra求两点间最短路径。由于每条边的权值必为正，故开始时就对连接Freddy点(源点)的所有边进行松弛，得出最小dict[]值的点s，其值便已确定，以后不会再改变(这点很重要，证明)。然后以s为源点，继续这样的操作，直至Freddy这点的dict[]值被确定。最坏情况下，每条边都访问一次，时间复杂度为0(n^2)。

注意两点：1：是先输入边数，再输入顶点数。  2：有重边的出现。

源代码：(4096K 32MS)

#include<iostream>
using namespace std;
const int Max = 1002;
const int inf = 0xfffff;

int n, edge[Max][Max], dict[Max];
bool vis[Max];

void init_data(){
    vis[1] =
true;
    for(int i =
2; i <= n; i ++)
       
dict[i] = inf;
}

int dijkstra(){
    int now = 1,
count = n - 1;
    while(count
--){
       
int k, min_dis = inf;
       
for(int i = 2; i <= n; i ++)
           
if(!vis[i]){  
 //  对还没确定dict[]的边进行松弛，同时寻找这一次的最短边和新加的顶点。

              
 if(edge[now][i] != 0
&& dict[i] >
dict[now] + edge[now][i])
                   
dict[i] = dict[now] + edge[now][i];
              
 if(min_dis > dict[i])
                  
 min_dis = dict[k = i]; 
          
 }
       
if(k == n) break;  // 
若第n点已被访问，则说明已得到点1到点n的最短路径。跳出。
       
now = k;
       
vis[k] = true;
    }
    return
dict[n];
}

int main(){
    int t;
    scanf("%d
%d", &t, &n);
   
init_data();
    while(t
--){
       
int u, v, val;
       
scanf("%d %d %d", &u, &v,
&val);
       
if(edge[u][v] == 0 || val <
edge[u][v]){   //
输入要进行重边的判断。
           
edge[u][v] = val;
           
edge[v][u] = val;
       
}
    }
   
printf("%dn", dijkstra());
    return
0;
}