LightOJ1002---Country Roads (最短路变形) - c++编程基础

TOP

LightOJ1002---Country Roads (最短路变形)

2015-11-21 01:00:25 来源: 作者: 【大中小】浏览:2次

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

For example, in the above picture, if we want to go from 0 to 4, then we can choose

1) 0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2) 0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3) 0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.
Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000) indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.
Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print ‘Impossible’.
Sample Input

Output for Sample Input

5 6

0 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

5 4

0 1 5

0 1 4

2 1 3

3 4 7

Case 1:

Case 2:

Impossible

Impossible
Note

Dataset is huge, user faster I/O methods.

dijkstra算法变形

/*************************************************************************
  > File Name: LightOJ1002.cpp
  > Author: ALex
  > Mail: zchao1995@gmail.com
  > Created Time: 2015年06月02日 星期二 19时34分01秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; static const int N = 555; int dist[N]; priority_queue < PLL, vector
                  
                   , greater
                   
                     > qu; struct node { int nxt; int w; int to; }edge[40000]; bool vis[555]; int head[N], tot; void addedge(int from, int to, int w) { edge[tot].to = to; edge[tot].w = w; edge[tot].nxt = head[from]; head[from] = tot++; } void Dijkstra(int u, int n) { while (!qu.empty()) { qu.pop(); } for (int i = 0; i < n; ++i) { dist[i] = inf; } dist[u] = 0; qu.push(make_pair(dist[u], u)); while (!qu.empty()) { PLL tmp = qu.top(); qu.pop(); int s = tmp.second; int d = tmp.first; for (int i = head[s]; ~i; i = edge[i].nxt) { int t = edge[i].to; int w = edge[i].w; if (dist[t] > max(d, w)) { dist[t] = max(d, w); qu.push(make_pair(dist[t], t)); } } } } int main() { int t, icase = 1; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { head[i] = -1; } tot = 0; int u, v, w; for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } scanf("%d", &u); Dijkstra(u, n); printf("Case %d:\n", icase++); for (int i = 0; i < n; ++i) { if (dist[i] == inf) { printf("Impossible\n"); } else { printf("%d\n", dist[i]); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 10791 Minimum Sum LCM	下一篇：HDU2149 Public Sale(巴什博奕)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: