[POJ2387] Til the Cows Come Home(最短路)
传送门:POJ 2387 Til the Cows Come Home千万看清点数和路径数的输入顺序。否则。你会像我一样WA和RE一个下午。#include <iostream>#include <vector>#include <queue>#include <string.h>#define INF 0x3f3f3f3fus...
·
传送门:POJ 2387 Til the Cows Come Home
千万看清点数和路径数的输入顺序。否则。你会像我一样WA和RE一个下午。
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1024;
int n, t;
int dis[maxn], w[maxn][maxn];
int vis[maxn];
void spfa_bfs(int u)
{
for(int i = 1; i <= n; ++i)
dis[i] = INF, vis[i] = 0;
dis[u] = 0;
queue <int> q;
q.push(u);
vis[u] = 1;
while(!q.empty())
{
int cur = q.front();
q.pop();
vis[cur] = 0;
for(int i = 1; i <= n; ++i)
{
if(w[cur][i] && dis[i] > dis[cur]+w[cur][i])
{
dis[i] = dis[cur]+w[cur][i];
if(!vis[i])
{
q.push(i);
vis[i] = 1;
}
}
}
}
}
void read()
{
cin >> t >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
w[i][j] = (i == j) ? 0 : INF;
for(int i = 0; i < t; ++i)
{
int u, v, l;
cin >> u >> v >> l;
if(w[u][v] > l)
w[u][v] = w[v][u] = l;
}
}
void solve()
{
spfa_bfs(1);
cout << dis[n] << '\n';
}
int main()
{
read();
solve();
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)