[hihoCoder] #1089 : 最短路径·二:Floyd算法
2024-08-28 19:33:42
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
万圣节的中午,小Hi和小Ho在吃过中饭之后,来到了一个新的鬼屋!
鬼屋中一共有N个地点,分别编号为1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。
由于没有肚子的压迫,小Hi和小Ho决定好好的逛一逛这个鬼屋,逛着逛着,小Hi产生了这样的问题:鬼屋中任意两个地点之间的最短路径是多少呢?
提示:其实如果你开心的话,完全可以从每个节点开始使用Dijstra算法_(:з」∠)_。
输入
每个测试点(输入文件)有且仅有一组测试数据。
在一组测试数据中:
第1行为2个整数N、M,分别表示鬼屋中地点的个数和道路的条数。
接下来的M行,每行描述一条道路:其中的第i行为三个整数u_i, v_i, length_i,表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据,满足N<=10^2,M<=10^3, 1 <= length_i <= 10^3。
对于100%的数据,满足迷宫中任意两个地点都可以互相到达。
输出
对于每组测试数据,输出一个N*N的矩阵A,其中第i行第j列表示,从第i个地点到达第j个地点的最短路径的长度,当i=j时这个距离应当为0。
- 样例输入
-
5 12
1 2 967
2 3 900
3 4 771
4 5 196
2 4 788
3 1 637
1 4 883
2 4 82
5 2 647
1 4 198
2 4 181
5 2 665 - 样例输出
-
0 280 637 198 394
280 0 853 82 278
637 853 0 771 967
198 82 771 0 196
394 278 967 196 0
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std; int N, M;
vector<vector<int>> graph; void solve() {
for (int k = ; k <= N; ++k) {
for (int i = ; i <= N; ++i) {
for (int j = ; j <= N; ++j) {
if (graph[i][k] < INT_MAX && graph[k][j] < INT_MAX) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
for (int i = ; i <= N; ++i) {
for (int j = ; j <= N; ++j) {
cout << graph[i][j] << " ";
}
cout << endl;
}
} int main() {
while (cin >> N >> M) {
graph.assign(N+, vector<int>(N+, INT_MAX));
for (int i = ; i <= N; ++i) {
graph[i][i] = ;
}
int u, v, len;
for (int i = ; i <= M; ++i) {
cin >> u >> v >> len;
graph[u][v] = graph[v][u] = min(graph[u][v], len);
}
solve();
}
return ;
}
最新文章
- 已知服务器ftp的账号密码,求解数据库表的内容
- VC++ 在使用 CImage 的Draw 输入一个图像时,有时候会造成图像失真严重,解决的方法如下
- PMP 第六章 项目时间管理
- <;1 小玩意(覆盖效果)
- 用RPM包安装MySQL的默认安装路径问题
- 【LeetCode】165 - Compare Version Numbers
- 龙芯将两款 CPU 核开源,这意味着什么?
- 20169210《Linux内核原理与分析》第八周作业
- 【Daily】 2014-4-23
- uva 10003 Cutting Sticks (区间dp)
- epoll的LT和ET模式
- 微信小程序添加、删除class’
- leetCode in Java (一)
- DB Query Analyzer has been downloaded more than 100,000 times
- php 识别二维码(转载)
- linux scanf函数%d后加空白
- fiddler学习总结--利用fiddler快速模拟mock
- 走进JVM之一 自己编译openjdk源码
- 一个简单的日志函数C++
- Spring使用AspectJ注解和XML配置实现AOP
热门文章
- 线程池线程数与(CPU密集型任务和I/O密集型任务)的关系
- python多线程概念
- listView/GridView getChild获取不到的解决方法
- 【转】TCP/IP详解学习笔记(二)
- wepy - 与原生有什么不同(x.wpy)使用实例
- 算法笔记_174:历届试题 地宫取宝(Java)
- MySQL优化小案例:连接数
- MVC MVP MVVM 图解
- EXCEPTION-STRUTS2
- exception PLS-00403: expression &#39;V_END&#39; cannot be used as an INTO-target of a SELECT/FETCH statement