2819.
Travel
Time Limit: 1.0 Seconds
Memory Limit: 65536K
Total Runs: 1042
Accepted Runs: 458
There are N cities in this country, and some of them are connected by roads. Given two cities, can you find the shortest distance between them?
Input
The first line contains the number of test cases, then some test cases followed.
The first line of each test case contain two integers N and M (3 ≤ N ≤ 1000, M ≥ 0), indicating the number of cities and the number of roads. The next line contain two numbers S and T (S ≠ T), indicating the start point and the destination. Each line of the following M lines contain three numbers Ai, Bi and Ci (1 ≤ Ai,Bi ≤ N, 1 ≤ Ci ≤ 1000), indicating that there is a road between city Ai and city Bi, whose length is Ci. Please note all the cities are numbered from 1 to N.
The roads are undirected, that is, if there is a road between A and B, you can travel from A to B and also from B to A.
Output
Output one line for each test case, indicating the shortest distance between
S and
T. If there is no path between them, output -1.
Sample Input
2
3 3
1 3
1 2 10
2 3 20
1 3 50
3 1
1 3
1 2 10
Sample Output
30
-1
Problem Setter: RoBa
Source: TJU Programming Contest 2007
Submit
List Runs Forum Statistics
#include
<
iostream
>
#include
<
queue
>
#define
MAX 1002
using
namespace
std; typedef
struct
node {
int
di;
int
heap; node(){} node(
int
h,
int
d) { heap
=
h; di
=
d; } friend
bool
operator
<
(node a,node b) {
return
a.di
>
b.di; } }Point; priority_queue
<
Point
>
Q; Point temp;
int
n,m,dis[MAX],t,s,e;
int
edges[MAX][MAX];
bool
mark[MAX];
void
Init() {
int
i,j,a,b,ss; scanf(
"
%d%d
"
,
&
n,
&
m); scanf(
"
%d%d
"
,
&
s,
&
e);
for
(i
=
1
;i
<=
n;i
++
)
for
(j
=
1
;j
<=
n;j
++
) edges[i][j]
=-
1
;
while
(m
--
) { scanf(
"
%d%d%d
"
,
&
a,
&
b,
&
ss);
if
(edges[a][b]
==-
1
||
s
<
edges[a][b]) { edges[a][b]
=
ss; edges[b][a]
=
ss; } } }
void
Dijkstra(
int
s) {
int
i,j,k;
while
(
!
Q.empty()) Q.pop();
for
(i
=
1
;i
<=
n;i
++
) { dis[i]
=
edges[s][i];
if
(dis[i]
!=-
1
) { Q.push(node(i,dis[i])); } mark[i]
=
false
; } mark[s]
=
true
;
for
(i
=
1
;i
<
n;i
++
) { k
=-
1
;
while
(
!
Q.empty()) { temp
=
Q.top(); Q.pop();
if
(
!
mark[temp.heap]) { k
=
temp.heap;
break
; } }
if
(k
==-
1
) { printf(
"
-1\n
"
);
return
; }
for
(j
=
1
;j
<=
n;j
++
) {
if
(mark[j]
||
edges[k][j]
==-
1
)
continue
;
if
(dis[k]
+
edges[k][j]
<
dis[j]
||
dis[j]
==-
1
) { dis[j]
=
dis[k]
+
edges[k][j]; Q.push(node(j,dis[j])); } } } printf(
"
%d\n
"
,dis[e]); }
int
main() { cin
>>
t;
while
(t
--
) { Init(); Dijkstra(s); }
return
0
; }
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/14/1456968.html
