关于网友提出的“ ACM求助啊求最短距离的 老是错误”问题疑问，本网通过在网上对“ ACM求助啊求最短距离的 老是错误”有关的相关答案进行了整理，供用户进行参考，详细问题解答如下：
问题： ACM求助啊求最短距离的 老是错误
描述:ACM 最短路
Description
Tanvir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found that there is no brush in him room. So, he called Atiq to get a brush. But as usual Atiq refused to come. So, Tanvir decided to go to Atiq's house.
The city they live in is divided by some junctions. The junctions are connected by two way roads. They live in different junctions. And they can go to one junction to other by using the roads only.
Now you are given the map of the city and the distances of the roads. You have to find the minimum distance Tanvir has to travel to reach Atiq's house.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line. The next line contains two integers N (2 ≤ N ≤ 100) and M (0 ≤ M ≤ 1000), means that there are N junctions and M two way roads. Each of the next M lines will contain three integers u v w (1 ≤ u, v ≤ N, w ≤ 1000), it means that there is a road between junction u and v and the distance is w. You can assume that Tanvir lives in the 1st junction and Atiq lives in the Nth junction. There can be multiple roads between same pair of junctions.
Output
For each case print the case number and the minimum distance Tanvir has to travel to reach Atiq's house. If it's impossible, then print 'Impossible'.
Sample Input
2
3 2
1 2 50
2 3 10
3 1
1 2 40
Sample Output
Case 1: 60
Case 2: Impossible
我的代码是
#include
#include
using namespace std ;
struct Node
{
int beg ;//起点
long dis ;//距离
Node( int a , long b )
{
beg = a ;
dis = b ;
}
};
int map[110][110];
long minimum[110];
queue open;
int main()
{
int T ;
cin >> T ;
for( int z = 1 ; z <= T ; ++z )
{
int N , M;
cin >> N >> M ;//N个点M条线
for( int i = 0 ; i <= N ; ++i )
{
minimum[i] = 1000000000 ;
for( int j = 0 ; j <= N ; ++j )
map[i][j] = 0 ;
}
for( int i = 1 ; i <= M ; ++i )
{
int u , v , w ;
cin >> u >> v >> w ;
map[u][v] = w ;
map[v][u] = w ;
}
open.push ( Node ( 1 , 0 ));
minimum[1] = 0 ;
while( !open.empty () )
{
int beg , dis;
beg = open.front ().beg ;
dis = open.front ().dis ;
open.pop ();
if( beg == N )//已经是终点了
continue ;
for( int i = 1 ; i <= N ; ++i )
if( ( map[beg][i] != 0 ) && ( map[beg][i] + dis < minimum[i] )) //找到节点
{
open.push( Node( i ,map[beg][i] + dis ));
minimum[i] = map[beg][i] + dis;
}
}
if( minimum[N] == 1000000000 )
cout << "Case " << z << ": Impossible" << endl;
else
cout << "Case " << z << ": "<< minimum[N] << endl;
}
}
解决方案1: 请注意：There can be multiple roads between same pair of junctions.
请试以下输入：
1
2 2
1 2 10
1 2 20
以上介绍了“ ACM求助啊求最短距离的 老是错误”的问题解答，希望对有需要的网友有所帮助。
本文网址链接：http://www.codes51.com/itwd/3716899.html
