poj 1797 Heavy Transportation
8899 ワード
タイトルリンク:
http://poj.org/problem?id=1797
タイトルの説明:
n個の交差点、m個の道路があり、各道路には3つの属性がある:始点、終点、最大荷重.aからbまでの最大荷重がa—>bから荷重できる最大重量であると仮定し、1—>nからの最大荷重はいくらですか?
問題解決の考え方:
dijkstraの変形を利用して、dist配列に格納されているのは最短経路ではなく、最大荷重であり、説明がはっきりしていないかもしれないが、コードははっきりしている.
ps:似たようなテーマは今年の省試合で見たことがありますが、当時は図に触れたばかりなので、ソート+で調べようと思っていましたが、このテーマのやり方は多く、この2つだけではありません.
http://poj.org/problem?id=1797
タイトルの説明:
n個の交差点、m個の道路があり、各道路には3つの属性がある:始点、終点、最大荷重.aからbまでの最大荷重がa—>bから荷重できる最大重量であると仮定し、1—>nからの最大荷重はいくらですか?
問題解決の考え方:
dijkstraの変形を利用して、dist配列に格納されているのは最短経路ではなく、最大荷重であり、説明がはっきりしていないかもしれないが、コードははっきりしている.
ps:似たようなテーマは今年の省試合で見たことがありますが、当時は図に触れたばかりなので、ソート+で調べようと思っていましたが、このテーマのやり方は多く、この2つだけではありません.
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <iostream>
6 using namespace std;
7 #define maxn 1010
8
9 int n, m;
10 int map[maxn][maxn], vis[maxn], dist[maxn];
11 void dijkstra ();
12
13 int main ()
14 {
15 int i, j, l = 0, a, b, s, ncase;
16 scanf ("%d", &ncase);
17
18 while (ncase --)
19 {
20 scanf ("%d %d", &n, &m);
21 memset (map, 0, sizeof(map));//
22
23 for (i=0; i<m; i++)
24 {
25 scanf ("%d %d %d", &a, &b, &s);
26 map[a][b] = map[b][a] = s;
27 }
28
29 dijkstra ();
30 printf ("Scenario #%d:
", ++l);
31 printf ("%d
", dist[n]);
32 }
33 return 0;
34 }
35
36 void dijkstra ()
37 {
38 int i, j, temp, index;
39
40 memset (vis, 0, sizeof(vis));
41 for (i=1; i<=n; i++)// dist
42 dist[i] = map[1][i];
43 vis[1] = 1;//
44
45 for (i=1; i<n; i++)
46 {
47 temp = 0;
48 for (j=1; j<=n; j++)//
49 if (!vis[j] && temp < dist[j])
50 {
51 temp = dist[j];
52 index = j;
53 }
54
55 vis[index] = 1;//
56
57 for (j=1; j<=n; j++)//
58 {
59 if (!vis[j] && map[index][j])
60 {
61 temp = min(dist[index], map[index][j]);// j ,
62 if (temp > dist[j])// j ,
63 dist[j] = temp;
64 }
65 }
66 }
67 }