1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| import java.util.*;
import java.io.*;
public class Main{
static int n,m,k;
static int N=(int)(2e5+10);
public static void main(String[] args) {
n=in.nextInt();
m=in.nextInt();
for(int i=1;i<=m;i++) {
int a=in.nextInt();
int b=in.nextInt();
int c=in.nextInt();
add(a,b,c);
}
int base[]=new int[N];
Arrays.fill(base,Integer.MAX_VALUE);
base[1]=0;
boolean val[]=new boolean[N];
Queue<Integer> qu=new LinkedList<>();
qu.add(1);
boolean flag=true;
int cnt[]=new int[N];
while(!qu.isEmpty()) {
int i=qu.poll();
val[i]=false;
if(node[i]==null) continue;
for(int poll[]:node[i]) {
int v=poll[0],w=poll[1];
if(base[v]>base[i]+w) {
base[v]=base[i]+w;
cnt[v]=cnt[i]+1;
if(cnt[v]>=n) {
qu.clear();
flag=false;
break;
}
if(!val[v]) {
qu.add(v);
val[v]=true;
}
}
}
}
if(flag&&base[n]==Integer.MAX_VALUE) out.println("impossible");
else out.println(base[n]);
out.flush();
}
static ArrayList<int[]> node[]=new ArrayList[N];
public static void add(int a,int b,int c) {
if(node[a]==null) node[a]=new ArrayList<>();
node[a].add(new int[] {b,c});
}
static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static input in=new input();
static class input{
static BufferedReader br;
static StringTokenizer st;
input(){
br=new BufferedReader(new InputStreamReader(System.in));
}
String next() {
String str="";
while(st==null||!st.hasMoreElements()) {
try {
str=br.readLine();
}catch(Exception e) {
e.printStackTrace();
}
st=new StringTokenizer(str);
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
}
|
