Description
Tom is a student in Shan Dong Normal University! his University in the suburbs,this day,Tom wanted to go to the downtown to visit his old friend Jerry,But tom faced a problem ,he want to know how to reach the city center fastest,now the bus stations of city are n[2,100], there are m[1,1000] bus routes in the city
Tom in the 1st bus station,Jerry in the Nth bus station
Input
The fist line is m,n;
Next m lines is a,b,c (a,b is the name of bus station , c is the time you cost from station a to station b)
Output
The shortest time tom reach city center
Sample Input
1 2
1 2 10
3 4
1 2 10
2 3 10
3 4 10
Sample Output
10
30
Source
Unknown
#include <cstdio>
#include <iostream>
#include <cmath>
#include <
string>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int inf =
0x3f3f3f3f;
const int maxn = 1e3+
8;
int n, m, cost[maxn][maxn], time[maxn];
bool sign[maxn];
void dij(
int s)
{
fill(time, time+n+
1, inf);
fill(sign, sign+n+
1,
0);
time[1] =
0;
for(
int i =
1; i <= n; i++
)
{
int miao, ying =
inf;
for(
int j =
1; j <= n; j++
)
if(!sign[j] && time[j] <=
ying)
ying = time[miao =
j];
sign[miao] =
1;
for(
int j =
1; j <= n; j++
)
if(time[j]>time[miao]+
cost[miao][j])
time[j] = time[miao]+
cost[miao][j];
}
}
int main()
{
while(~scanf(
"%d%d", &m, &n) && (n+
m))
{
for(
int i =
1; i <= n; i++
)
for(
int j =
1; j <= n; j++
)
cost[i][j] =
inf;
int a, b, c;
while(m--
)
{
scanf("%d%d%d", &a, &b, &
c);
if(cost[a][b]>
c)
cost[a][b] = cost[b][a] =
c;
}
dij(1);
printf("%d\n", time[n]);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11536063.html
相关资源：JAVA上百实例源码以及开源项目
