\color{Red}{信使——【由复杂度选择合适的图论算法】}
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
解析
这道题难点不在于选什么算法,其实这道题数据量 n <= 100
,选最坏的代码最少的多源最短路 floyd
,也只需要最坏的情况下为 1 * 10 ^ 6
,可以在 1秒内ac。
一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下,代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8
为最佳。
n <= 100
-> O(n ^ 3)
-> 状态压缩dp floyd 高斯消元
n <= 1000
-> O(n ^ 2)
O(n ^ 2 * log(n))
-> dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
n ≤ 100000
-> O(nlogn)
-> 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa
这道题难点在于能抽象出如何用图论解,第一直觉-> bfs,开二维PII或者类【结构体】存是否来过及距离,逐层bfs,如果走过【对象的属性有过赋值】就不入队。
但是还是可以进一步优化,在这里其实就意识到,这道题是最短路,因为每个点到起点的最小距离就是它最快受到信的情况,而如果无法到达起点,就直接判定失败输出-1。
故根据上面的复杂度,选择代码最少的 floyd
。
我的SPFA全题解
我的Dijkstra全题解
我的Bellman_fold全题解
我的Floyd全题解
floyd
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, m, N = 110;
static int[][] g = new int[N][N];
static final int INF = 0x3f3f3f3f;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
g[a][b] = g[b][a] = Math.min(g[a][b], c);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (g[1][i] == INF) {
System.out.println(-1);
return;
} else {
ans = Math.max(ans, g[1][i]);
}
System.out.println(ans);
}
}