HDU 4370 0 or 1——spfa

HDU 4370 0 or 1——spfa

很抽象的最短路，想了很久也没有想出来，最后看了别人的博客还是似懂非懂，这里推荐一篇：

​

#include #include #include #include #include using namespace std;const int maxn = 500;const int INF = 0x3f3f3f3f;bool vis[maxn];int N, G[maxn][maxn], dis[maxn];void spfa(int s) { for (int i = 1; i <= N; i++) dis[i] = INF, vis[i] = false; queue q; for (int i = 1; i <= N; i++) { if (s == i) continue; dis[i] = G[s][i]; vis[i] = true; q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = 1; i <= N; i++) { if (dis[i] > dis[u] + G[u][i]) { dis[i] = dis[u] + G[u][i]; if (!vis[i]) { vis[i] = true; q.push(i); } } } }}int main () { while (~scanf("%d", &N)) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &G[i][j]); } } spfa(1); int ans1 = dis[N]; int ans2 = dis[1]; spfa(N); int ans3 = dis[N]; printf("%d\n", min(ans1, ans2 + ans3)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。