DAY60Bellman_ford 算法
队列优化算法
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。
如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 “unconnected”。
import java.util.*;
public class Test {
static class Edge{
int from;
int to;
int val;
public Edge(int from,int to,int val){
this.from=from;
this.to=to;
this.val=val;
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
List<List<Edge>> graph=new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
for(int i=0;i<m;i++){
int from=in.nextInt();
int to=in.nextInt();
int val=in.nextInt();
graph.get(from).add(new Edge(from, to, val));
}
int[]minDist=new int[n+1];
Arrays.fill(minDist,Integer.MAX_VALUE);
minDist[1]=0;
Queue<Integer> queue=new LinkedList<>();
queue.offer(1);
boolean[] isInQueue=new boolean[n+1];
while(!queue.isEmpty()){
int curNode=queue.poll();
isInQueue[curNode]=false;
for(Edge edge:graph.get(curNode)){
if(minDist[edge.to]>minDist[edge.from]+edge.val){
minDist[edge.to]=minDist[edge.from]+edge.val;
if(!isInQueue[edge.to]){
queue.offer(edge.to);
isInQueue[edge.to]=true;
}
}
}
}
if(minDist[n]==Integer.MAX_VALUE){
System.out.println("unconnected");
}else{
System.out.println(minDist[n]);
}
}
}
判断负权回路
负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。
import java.util.*;
public class Test {
static class Edge{
int from;
int to;
int val;
public Edge(int from,int to,int val){
this.from=from;
this.to=to;
this.val=val;
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
List<List<Edge>> graph=new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
for(int i=0;i<m;i++){
int from=in.nextInt();
int to=in.nextInt();
int val=in.nextInt();
graph.get(from).add(new Edge(from, to, val));
}
int[]minDist=new int[n+1];
Arrays.fill(minDist,Integer.MAX_VALUE);
minDist[1]=0;
Queue<Integer> queue=new LinkedList<>();
queue.offer(1);
boolean[] isInQueue=new boolean[n+1];
int[] count=new int[n+1];
count[1]++;
boolean flag=false;
while(!queue.isEmpty()){
int curNode=queue.poll();
isInQueue[curNode]=false;
for(Edge edge:graph.get(curNode)){
if(minDist[edge.to]>minDist[edge.from]+edge.val){
minDist[edge.to]=minDist[edge.from]+edge.val;
if(!isInQueue[edge.to]){
queue.offer(edge.to);
count[edge.to]++;
isInQueue[edge.to]=true;
}
if(count[edge.to]==n){
flag=true;
while (!queue.isEmpty()) {
queue.poll();
}
break;
}
}
}
}
if(flag){
System.out.println("circle");
}else if(minDist[n]==Integer.MAX_VALUE){
System.out.println("unconnected");
}else{
System.out.println(minDist[n]);
}
}
}
加了一个count数组，若松弛 n 次以上，则存在负权回路
单源有限最短路
某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。
网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。
权值为正表示扣除了政府补贴后运输货物仍需支付的费用；
权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。
请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本
import java.util.*;
public class Main {
// 基于Bellman_for一般解法解决单源最短路径问题
// Define an inner class Edge
static class Edge {
int from;
int to;
int val;
public Edge(int from, int to, int val) {
this.from = from;
this.to = to;
this.val = val;
}
}
public static void main(String[] args) {
// Input processing
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<Edge> graph = new ArrayList<>();
for (int i = 0; i < m; i++) {
int from = sc.nextInt();
int to = sc.nextInt();
int val = sc.nextInt();
graph.add(new Edge(from, to, val));
}
int src = sc.nextInt();
int dst = sc.nextInt();
int k = sc.nextInt();
int[] minDist = new int[n + 1];
int[] minDistCopy;
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0;
for (int i = 0; i < k + 1; i++) { // Relax all edges k + 1 times
minDistCopy = Arrays.copyOf(minDist, n + 1);
for (Edge edge : graph) {
int from = edge.from;
int to = edge.to;
int val = edge.val;
// Use minDistCopy to calculate minDist
if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) {
minDist[to] = minDistCopy[from] + val;
}
}
}
// Output printing
if (minDist[dst] == Integer.MAX_VALUE) {
System.out.println("unreachable");
} else {
System.out.println(minDist[dst]);
}
}
}