JAVA 代码
import java.io.*;
import java.util.*;
class Main{
static class Edge{
int a, b, w;
Edge(int a, int b, int w){
this.a = a; this.b = b; this.w = w;
}
}
static int n, m, k;
static int M = 100010, N = 510, INF = 0x3f3f3f3f;
static Edge[] edges = new Edge[M];
static int[] dist = new int[N];
static int[] backup = new int[N];
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static int bellmanFord(){
Arrays.fill(dist, INF);
dist[1] = 0;
for(int i = 0; i < k; i++){
backup = dist.clone();
for(int j = 0; j < m; j++){
int a = edges[j].a;
int b = edges[j].b;
int w = edges[j].w;
dist[b] = Math.min(dist[b], backup[a] + w);
}
}
if(dist[n] > INF / 2) return -1;
return dist[n];
}
public static void main(String[] args) throws Exception{
String[] s = read.readLine().split(" ");
n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]);
k = Integer.valueOf(s[2]);
for(int i = 0; i < m; i++){
s = read.readLine().split(" ");
int a = Integer.valueOf(s[0]);
int b = Integer.valueOf(s[1]);
int w = Integer.valueOf(s[2]);
edges[i] = new Edge(a, b, w);
}
int t = bellmanFord();
if(t == -1) System.out.println("impossible");
else System.out.println(t);
}
}
时间复杂度
O(k * m)
哈哈,那是不是应该定义为final
可以的哈哈,刷题没那么讲究。
为什么是static int M = 100010, N = 510, INF = 0x3f3f3f3f;而不是const
这个是java, java没有const哈,您是不是以为是c++代码了。