鱼C论坛

 找回密码
 立即注册
查看: 2738|回复: 2

ACM求助关于最小路径的老是WA

[复制链接]
发表于 2013-1-24 23:14:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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



我的代码
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std ;
  4. struct Node
  5. {
  6.    int beg ;//起点
  7.    long dis ;//距离
  8.    Node( int a , long b )
  9.    {
  10.       beg = a ;
  11.       dis = b ;
  12.    }
  13. };
  14. int map[110][110];
  15. long minimum[110];
  16. queue<Node> open;
  17. int main()
  18. {
  19.    int T ;
  20.    cin >> T ;
  21.    for( int z = 1 ; z <= T ; ++z )
  22.    {
  23.        int N ,  M;
  24.        cin >> N >> M ;//N个点M条线
  25.        for( int i = 0 ; i <= N ; ++i )
  26.        {
  27.           minimum[i] = 1000000000 ;
  28.           for( int j = 0 ; j <= N ; ++j )
  29.             map[i][j] = 0 ;
  30.        }
  31.       
  32.        for( int i = 1 ; i <= M ; ++i )
  33.        {
  34.           int u , v , w ;
  35.           cin >> u >> v >> w ;
  36.           map[u][v] = w ;
  37.           map[v][u] = w ;  
  38.        }
  39.        open.push ( Node ( 1 , 0 ));
  40.         minimum[1] = 0 ;
  41.        while( !open.empty () )
  42.        {
  43.           int beg , dis;
  44.           beg = open.front ().beg ;
  45.           dis = open.front ().dis ;
  46.           open.pop ();
  47.           if( beg == N )//已经是终点了
  48.             continue ;
  49.           for( int i = 1 ; i <= N ; ++i )
  50.              if( ( map[beg][i] != 0 ) && ( map[beg][i] + dis < minimum[i] )) //找到节点
  51.               {
  52.                  open.push( Node( i ,map[beg][i] + dis ));
  53.                  minimum[i] = map[beg][i] + dis;
  54.               }
  55.          
  56.        }
  57.       
  58.        if( minimum[N] == 1000000000 )
  59.          cout << "Case " << z << ": Impossible" << endl;
  60.        else
  61.          cout << "Case " << z << ": "<< minimum[N] << endl;         
  62.    }
  63. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-25 00:02:11 | 显示全部楼层
我来灌水  支持程序讨论
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-25 01:58:05 | 显示全部楼层
弱弱的问一句,您是在考验各位的英语能力吗?!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 21:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表