#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN =
5000, MAXE =
21474836;
struct Edge
{
int from, to, cost;
}es[MAXN <<
2];
int first[MAXN <<
2], next[MAXN <<
2], tot, d[MAXN];
int t, c, te, ts;
bool used[MAXN];
queue < int > q;
void build(
int f,
int t,
int d)
{
es[++tot].from = f;
es[tot].to = t;
es[tot].cost = d;
next[tot] = first[f];
first[f] = tot;
}
void spfa(
int s)
{
d[s] =
0;
q.push(s);
used[s] =
1;
while(!q.empty())
{
int x = q.front();
q.pop();
used[x] =
0;
for(
int i = first[x]; i != -
1; i = next[i])
{
int u = es[i].to;
if(d[u] > d[x] + es[i].cost)
{
d[u] = d[x] + es[i].cost;
if(!used[u])
{
q.push(u);
used[u] =
1;
}
}
}
}
}
int main()
{
scanf(
"%d%d%d%d", &t, &c, &ts, &te);
memset(first, -
1,
sizeof(first));
for(
int i =
1; i <= c; i++)
{
int rs, re, ci;
scanf(
"%d%d%d", &rs, &re, &ci);
build(rs, re, ci);
build(re, rs, ci);
}
memset(d,
0x3f,
sizeof(d));
spfa(ts);
cout<<d[te];
return 0;
}
转载于:https://www.cnblogs.com/Loi-Vampire/p/6017072.html
相关资源：JAVA上百实例源码以及开源项目
