1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,mapp[505][505],f[100009];
 4 bool vis[505];
 5 long long dij(){
 6     memset(f,0x3f,sizeof(f));
 7     f[1]=0;
 8     for(int j=1;j<=n;j++){
 9         int t=-1;
10         for(int i=1;i<=n;i++){
11             if(vis[i]==false){
12                 if(t==-1) t=i;
13                 else if(f[i]<f[t]) t=i;
14             }
15         }
16         vis[t]=true;
17         for(int i=1;i<=n;i++){
18             f[i]=min(f[i],f[t]+mapp[t][i]);
19         }
20     }
21     if(f[n]==0x3f3f3f3f) return -1;
22     return f[n];
23 }
24 int main(){
25     cin>>n>>m;
26     memset(mapp,0x3f,sizeof(mapp));
27     for(int i=1;i<=m;i++){
28         int be,en,wei;
29         cin>>be>>en>>wei;
30         mapp[be][en]=min(mapp[be][en],wei);
31     }
32     for(int i=1;i<=n;i++){
33         mapp[i][i]=0;
34     }
35     int t=dij();
36     cout<<t;
37     return 0;
38 } 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+10,M=2e6+10;
 4 struct node{
 5     int to,next,val;    
 6 }edge[M];
 7 typedef pair<int,int> PII;
 8 priority_queue<PII,vector<PII>,greater<PII> > q;
 9 int h[N],idx=0,dist[N],n,m;
10 bool st[N];
11 void add(int x,int y,int z){
12     edge[idx].to=y;edge[idx].val=z;
13     edge[idx].next=h[x];h[x]=idx++;
14 }
15 void dijkstra(){
16     memset(dist,0x3f,sizeof(dist));
17     dist[1]=0;
18     q.push({0,1});
19     while(!q.empty()){
20         PII t=q.top();
21         q.pop();
22         int dis=t.first,u=t.second;
23         if(st[u]) continue;
24         st[u]=true;
25         for(int i=h[u];i!=-1;i=edge[i].next){
26             int j=edge[i].to;
27             if(dist[j]>edge[i].val+dis){
28                 dist[j]=edge[i].val+dis;
29                 q.push({dist[j],j});
30             }
31         }
32     }
33 }
34 int main(){
35     cin>>n>>m;
36     memset(h,-1,sizeof(h));
37     for(int i=1;i<=m;i++){
38         int u,v,w;
39         cin>>u>>v>>w;
40         add(u,v,w);
41     }
42     dijkstra();
43     if(dist[n]>0x3f3f3f3f/2) cout<<-1;
44     else cout<<dist[n];
45     return 0;
46 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=0x3f3f3f3f;
 4 int fl[300][300];
 5 int n,m,k;
 6 void f(){
 7     for(int ii=1;ii<=n;ii++){
 8         for(int i=1;i<=n;i++){
 9             for(int j=1;j<=n;j++){
10                 fl[i][j]=min(fl[i][j],fl[i][ii]+fl[ii][j]);
11             }
12         }
13     }
14 }
15 int main(){
16     cin>>n>>m>>k;
17     int a,b,c;
18     memset(fl,N,sizeof(fl));
19     for(int i=1;i<=m;i++){
20         cin>>a>>b>>c;
21         fl[a][b]=min(c,fl[a][b]);
22     }
23     for(int i=1;i<=n;i++){
24         fl[i][i]=0;
25     }
26     f();
27     for(int i=1;i<=k;i++){
28         cin>>a>>b;
29         if(fl[a][b]==N)cout<<"impossible"<<endl;
30         else cout<<fl[a][b]<<endl;
31     }
32     return 0;
33 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100009,M=200009;
 4 int ver[100009],edge[M],nex[M],head[N],tot;
 5 int n,m,f[N];
 6 bool vis[N];
 7 void add(int x,int y,int z){
 8     ver[++tot]=y;edge[tot]=z;
 9     nex[tot]=head[x],head[x]=tot;
10 }
11 int SPFA(){
12     memset(f,0x3f,sizeof(f));
13     queue<int> q;
14     f[1]=0;
15     vis[1]=true;
16     q.push(1);
17     while(!q.empty()){
18         int x=q.front();
19         q.pop();
20         vis[x]=false;
21         for(int i=head[x];i;i=nex[i]){
22             int j=ver[i];
23             if(f[j]>f[x]+edge[i]){
24                 f[j]=f[x]+edge[i];
25                 if(vis[j]==false){
26                     vis[j]=true;
27                     q.push(j);
28                 }
29             }
30         }
31     }
32     if(f[n]==0x3f3f3f3f) return -1;
33     return f[n];
34 }
35 int main(){
36     cin>>n>>m;
37     for(int i=1;i<=m;i++){
38         int from,to,z;
39         cin>>from>>to>>z;
40         add(from,to,z);
41     }
42     int z=SPFA();
43     if(z==-1) cout<<"impossible";
44     else cout<<z;
45     return 0;
46 }