JAVA AC代码:
有负权边的最短路问题处理:
规定了最多通过几条边用Bellman-ford
没有规定则用spfa

import java.util.*;
import java.util.StringTokenizer;
import java.io.*;

public class Main {
	//Edge类,一个对象代表一条边
	static class Edge{
		//点u到点v有一条边权为w的路线（单向）
		int u,v,w;
		public Edge(int u,int v,int w){
			this.u=u;
			this.v=v;
			this.w=w;
		}
	}

	public static void main(String[] args) {
		int n=in.nextInt(),m=in.nextInt(),k=in.nextInt();
		int[] dist=new int[n+1];//记录原点到第i个位置的距离
		final int INF=0x3f3f3f3f;//int最大值
		Arrays.fill(dist,INF);//把所有点都设置为不可到达
		dist[1]=0;//原点到本身的距离为0
		//数据读入
		List<Edge> edge=new ArrayList<>();	
		while(m-->0){
			int u=in.nextInt();
			int v=in.nextInt();
			int w=in.nextInt();
			edge.add(new Edge(u,v,w));
		}
		//遍历k次->最多经过k条边；第i次代表经过最多i条边
		for(int i=0;i<k;i++){
			//将原来的dist复制，使得predist中的数据是最多遍历i-1条边的数据
			int [] predist=Arrays.copyOf(dist, dist.length);
			//检查是否有更新数组，如果没有更新则说明多的边都是多余的
			//如果没有更新，则dist和predist在下次循环中的值相同，下面操作也是重复的
			boolean flag=false;
			for(Edge e:edge){
				//最多遍历i-1条边的时候能到u点，并且i-1->u的距离加上u->w的距离比原点到v的距离小
				//这里要用dist[];因为dist正在更新当前最多通过第i条边的最短路
				//可能会有多条路径，使得最多通过i条边的路径都比最多通过i-1条边的路径小
				//如果用predist[];就会导致dist[]中存的不一定是最短路，而是最后遍历（比通过i-1条边路径小）的那条路
				if(predist[e.u]!=INF&&predist[e.u]+e.w<dist[e.v]){
					//给dist[]赋值
					dist[e.v]=predist[e.u]+e.w;
					//记录数组更新了
					flag=true;
				}
			}
			//数组没有更新，后面的循环为无效循环，直接退出
			if(!flag) break;
		}
		//如果dist[n]的值很大，直接输出到不了该点
		if(dist[n]>INF/2) out.println("impossible");
		else out.println(dist[n]);
		out.close();

	}
	
	

	static FastReader in=new FastReader();
	static PrintWriter out=new PrintWriter(System.out);
	static class FastReader{
		static BufferedReader br;
		static StringTokenizer st;
		FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			String str="";
			while(st==null||!st.hasMoreElements()) {
				try {
					str=br.readLine();
				}catch(IOException e) {
					throw new RuntimeException(e);
				}
				st=new StringTokenizer(str);
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
}