题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示点x和点y之间存在一条有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出”impossible”。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
样例
输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N = 100010;
static int n;
static int m;
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 idx = 0;
static int[] dist = new int[N];
static boolean[] st = new boolean[N]; //标记是否在队列中
static int INF = 0x3f3f3f3f;
public static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static int spfa()
{
Arrays.fill(dist, INF);
Queue<Integer> queue = new LinkedList<Integer>();
dist[1] = 0;
queue.add(1);
st[1] = true;//标记1号点在队列中
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];
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
add(a,b,c);
}
int t = spfa();
if(t == 0x3f3f3f3f) System.out.println("impossible");
else System.out.println(t);
}
}