ZOJ Problem Set - 2281
Way to Freedom
Time Limit: 2 Seconds
Memory Limit: 32768 KB
Background
"Now, you are getting closer and closer to Your Gate to Freedom!
And you will pass the most dangerous paths! Be careful!"
We're in a maze now. There're many rooms floating in the sky connected with wooden bridges. Bridges seems unstable...
Problem
At first, I'm in room X, and I want to go to room Y. There're N (N <= 100,000) rooms connected with M (M <= 1,000,000) edges. Each edge has a limit of weight, if weight exceeds this value, the edge will split, and drop me into the river.
How many things I can take to room Y at most?
Input
This problem contains multiple test cases.
Each test case begins with two integers N and M, then M lines, each line has 3 numbers: X, Y and Weight (<=2,000,000,000).
Output
For each test case, output the maximum weight I can take.
Sample Input
6 6 1 5 2000 2 4 5000 2 5 3300 3 4 2400 3 6 2200 4 6 6000 3 5
Sample Output
2400
Author: JIANG, YanyanContest: A Great Beloved and My Gate to Freedom There is a cx, there is a love_cx.
Source:
JIANG, Yanyan's Contest #2
Submit
Status
//
1838048 2009-04-19 12:27:25 Accepted 2281 C++ 580 6588 Wpl
//
更牛的Dijkstra+优先队列解决最大网络流问题
#include
<
iostream
>
#include
<
queue
>
#include
<
vector
>
#define
MAX 100005
using
namespace
std; typedef
struct
node {
int
heap;
int
dis; node() {} node(
int
h,
int
d) { heap
=
h; dis
=
d; } friend
bool
operator
<
(node a,node b)
//
用的是大堆
{
return
a.dis
<
b.dis; } }Point; priority_queue
<
Point
>
Q; Point temp; vector
<
Point
>
G[MAX];
int
n,m,start,end,dis[MAX],zz
=
1
;
void
Init() {
int
i,a,b,s;
for
(i
=
1
;i
<=
n;i
++
)
//
初始化
G[i].clear();
while
(m
--
) { scanf(
"
%d%d%d
"
,
&
a,
&
b,
&
s); G[a].push_back(node(b,s)); G[b].push_back(node(a,s)); } scanf(
"
%d%d
"
,
&
start,
&
end); }
int
GetMin(
int
a,
int
b) {
if
(a
==-
1
)
return
b;
else
{
if
(a
>
b)
return
b;
else
return
a; } }
void
Dijkstra() {
int
i,tp,td,k;
for
(i
=
1
;i
<=
n;i
++
) { dis[i]
=-
1
; }
while
(
!
Q.empty()) Q.pop(); Q.push(node(start,
-
1
));
while
(
!
Q.empty()) { temp
=
Q.top(); k
=
temp.heap; Q.pop();
if
(k
==
end) { printf(
"
%d\n
"
,temp.dis);
return
; }
for
(i
=
0
;i
<
G[temp.heap].size();i
++
) { tp
=
G[temp.heap][i].heap; td
=
G[temp.heap][i].dis;
if
(GetMin(dis[k],td)
>
dis[tp]) { dis[tp]
=
GetMin(dis[k],td); Q.push(node(tp,dis[tp])); } } } printf(
"
0\n
"
); }
int
main() {
while
(scanf(
"
%d%d
"
,
&
n,
&
m)
!=
EOF) { Init(); Dijkstra(); }
return
0
; }
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/21/1485947.html
