1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
struct Node
{
int to;
long long len;
bool operator<(const Node &a) const
{
return len > a.len;
}
};
bool isUsed[510];
long long ans[510];
vector<Node> NodeQueue[510];
void addEdge(int s, int e, int len)
{
NodeQueue[s].push_back((Node){e,len});
NodeQueue[e].push_back((Node){s,len});
}
int n,m;
priority_queue<Node> PriNodeQueue;
int main()
{
scanf("%d%d", &n, &m);
while(m--)
{
int s, e, len;
scanf("%d%d%d",&s, &e, &len);
if(s != e)
addEdge(s, e, len);
}
int s, t;
scanf("%d%d", &s, &t);
for(int i = 0; i < 505; i++)
ans[i] = 999999999999;
ans[s] = 0;
PriNodeQueue.push((Node){s,0});
while(!PriNodeQueue.empty()){
Node now = PriNodeQueue.top();
PriNodeQueue.pop();
int u = now.to;
if(!isUsed[u]){
isUsed[u] = true;
for(int i = 0; i < NodeQueue[u].size(); i++){
if(!isUsed[NodeQueue[u][i].to]){
int v = NodeQueue[u][i].to;
int len = NodeQueue[u][i].len;
if(ans[v] > ans[u] + len)
{
ans[v] = ans[u] + len;
PriNodeQueue.push((Node){v,ans[v]});
}
}
}
}
}
printf("%lld",ans[t]);
return 0;
}
|