Roadblocks--poj3255（次短路）
时间：2021-07-01 10:21:17
帮助过：2人阅读
<cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
#define INF 0xfffffff
#define N 5060
struct Edge
{
int e,w;
Edge(int x=
0,
int y=
0):e(x),w(y){}
};
vector<Edge>
G[N];
int dist[N][
2], n, m, vis[N];
void spfa(
int s,
int k)
{
queue<Edge>
Q;
Edge p, q;
dist[s][k] =
0;
Q.push(Edge(s, 0));
while(Q.size())
{
p=
Q.front(); Q.pop();
vis[p.e] =
1;
int len =
G[p.e].size();
for(
int i=
0; i<len; i++
)
{
q =
G[p.e][i];
if(dist[q.e][k] > dist[p.e][k] +
q.w)
{
dist[q.e][k] = dist[p.e][k] +
q.w;
if(vis[q.e] ==
0)
{
Q.push(q);
vis[q.e] =
1;
}
}
}
}
}
int main()
{
int a, b, c;
while(scanf(
"%d%d", &n, &m)!=
EOF)
{
for(
int i=
0;i<=n;i++
)
{
G[i].clear();
dist[i][0]= dist[i][
1]=
INF;
}
for(
int i=
0; i<m;i++
)
{
scanf("%d%d%d", &a, &b, &
c);
G[a].push_back(Edge(b, c));
G[b].push_back(Edge(a, c));
}
spfa(1,
0);
spfa(n, 1);
int ans =
INF;
for(
int i=
1; i<=n; i++
)
{
int len =
G[i].size();
for(
int j=
0; j<len; j++
)
{
int W=G[i][j].w + dist[i][
0] +dist[G[i][j].e][
1];
if(ans>W && W>dist[n][
0])
{
ans=
W;
}
}
}
printf("%d\n", ans);
}
}
Roadblocks--poj3255（次短路）
标签：
