我更新过谁我就拿被更新的这个去更新别人
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<list>
using namespace std;
const int N=100010;
typedef pair<int,int>PII;
int n,m;
list<PII>h[N];
int spfa(){
int dist[N];
memset(dist,0x3f,sizeof dist);
queue<int>q;
bool in[N];
q.push(1);
in[1]=true;
dist[1]=0;
while(q.size()){
int t=q.front();
q.pop(),in[t]=false;
for(auto& e:h[t]){
if(dist[e.second]>dist[t]+e.first){
dist[e.second]=dist[t]+e.first;
if(!in[e.second]) q.push(e.second);
}
}
}
return dist[n];
}
int main(){
cin>>n>>m;
while(m--){
int a,b,d;
cin>>a>>b>>d;
h[a].push_back({d,b});
}
int res=spfa();
if(res>=0x3f3f3f3f/2)cout<<"impossible";
else cout<<res;
return 0;
}