AcWing 851. spfa求最短路java
原题链接
简单
作者:
huaqingren
,
2021-02-09 17:01:47
,
所有人可见
,
阅读 150
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main
{
private static int N=100010;
private static int n,m;
private static boolean[] st=new boolean[N];
private static int[] dist=new int[N];
private static List<Integer>[] g=new ArrayList[N];
private static Map<String,Integer> map=new HashMap<>();//存储两点之间的权重值
private static int max=100000000;
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
for(int i=1;i<=n;i++)
g[i]=new ArrayList<>();
for(int i=0;i<m;i++)
{
int a=scan.nextInt();
int b=scan.nextInt();
int c=scan.nextInt();
g[a].add(b);
String s=a+"+"+b;
map.put(s, c);
}
int t=spfa();
if(t==max)
System.out.println("impossible");
else
System.out.println(t);
scan.close();
}
private static int spfa()
{
for(int i=1;i<=n;i++)
dist[i]=max;
dist[1]=0;
Queue<Integer> queue=new LinkedList<>();
queue.offer(1);
st[1]=true;
while(!queue.isEmpty())
{
int t=queue.poll();
st[t]=false;
for(int i=0;i<g[t].size();i++)
{
int j=g[t].get(i);
int w=max;
//获取t->j这条边的权重值
String s=t+"+"+j;
if(map.get(s)!=null)
w=map.get(s);
if(dist[j]>dist[t]+w)
{
dist[j]=dist[t]+w;
if(!st[j])
{
queue.offer(j);
st[j]=true;
}
}
}
}
return dist[n];
}
}