题目

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。数据保证不存在负权回路。

输入格式

第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式

输出一个整数，表示1号点到n号点的最短距离。如果路径不存在，则输出"impossible”。

数据范围

$1\le n,m\le 10^5$,
图中涉及边长绝对值均不超过10000。

• 输入样例:

3 3
1 2 5
2 3 -3
1 3 4

• 输出样例:

2

题解

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;/*** @author akuya* @create 2023-07-06-19:36*/
public class spfa {static int N=100010;static int n,m,idx;static int x,y,z;static int h[]=new int[N];static int e[]=new int[N];static int ne[]=new int[N];static int w[]=new int[N];static int dist[]=new int[N];static boolean st[] =new boolean[N];public static void main(String[] args) {Scanner scanner=new Scanner(System.in );n=scanner.nextInt();m=scanner.nextInt();Arrays.fill(h,-1);while(m--!=0){x=scanner.nextInt();y=scanner.nextInt();z=scanner.nextInt();add(x,y,z);}int ans=spfa();if(ans==-1) System.out.println("impossible");else System.out.println(ans);}public static int spfa(){Arrays.fill(dist,0x3f3f3f);dist[1]=0;Queue<Integer> queue=new LinkedList();queue.add(1);st[1]=true;while(!queue.isEmpty()){int t=queue.poll();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){queue.add(j);st[j]=true;}}}}return dist[n]==0x3f3f3f?-1:dist[n];}public static void add(int a, int b ,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;}}

思路

spfa用于处理带负权的最短路，即使不带负权，大多数求最短路的题目都可以用spfa求解，很好用。求最短路思路与Dijkstra相似。但dijkstra算法的思想是每次找最短路，spfa的思想是不断对边进行松弛处理。并不需要每次找到最小，也就是没有试用贪心，便可处理负权。但同时也舍弃了速度。时间复杂度为（MN）