Hust oj 1635 ikki的旅行（Dij）_综合

ikki的旅行

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 72(28 users)

Total Accepted: 45(27 users)

Rating:

Special Judge: No

Description

为了更好的开展旅游计划，ikki找到一些自己想去的旅游景点。

ikki把所有可以直接相连的景点之间的距离都测量的了出来，但是由于时间紧迫，现在只能选择一个旅游景点去旅游，你能帮她计算出她选择的旅游景点和出发地之间的距离么？

Input

多组测试数据，对于每组测试数据，第一行两个正整数n,m(0 < n ≤ 200, 0 < m < n×(n-1)/2 ),其中n是地点的总数（1为出发点其它均为旅游的景点，n为ikki最终选择的旅游景点），m是已知的道路的数目，接下来的m行，每行3个整数想x,y,z表示x地区和y地区之间有一条长度为z的双向道路。

Output

对于每组测试数据，输出一个整数表示ikki去选择好的旅游景点所需要经过的最短距离，每组输出占一行。题目保证从出发点到目的地之间至少有一条路线。

Sample Input

3 3

1 2 1

2 3 1

1 3 3

Sample Output

floyd的话O（n^3）过不了,用dij可以过，注意节点从1开始编号

#include<cstdio>
#include<iostream>
using namespace std;const int maxn = 205;
const int Inf = 0x3f3f3f;
int map[maxn][maxn];
int dis[maxn];
int vis[maxn];
int n,m;
int x,y,z;void mapinit()
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i == j)map[i][j] = 0;elsemap[i][j] = Inf;}}
}void Arrayinit(int start)
{for(int i=1;i<=n;i++){dis[i] = map[start][i];vis[i] = 0;}
}
int Dijkstra(int start,int end)
{Arrayinit(start);vis[start] = 1;for(int i=1;i<=n;i++){int Min = Inf;int flag;for(int j=1;j<=n;j++){if(dis[j] < Min && !vis[j]){flag = j;Min = dis[j];}}vis[flag] = 1;for(int j=1;j<=n;j++){if(map[flag][j]+dis[flag] < dis[j] &&!vis[j])dis[j] = map[flag][j] + dis[flag];}}return dis[end];
}int main()
{while(~scanf("%d%d",&n,&m)){mapinit();int start,end;for(int i=0;i<m;i++){scanf("%d%d%d",&x,&y,&z);if(map[x][y] > z)map[x][y] = map[y][x] = z;}int ans = Dijkstra(1,n);printf("%d\n",ans);}return 0;
}