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
|
#define ka1 getchar() #define iis std::ios::sync_with_stdio(false) using namespace std; typedef long long LL; const int N = 100005; const int INF = 0x3f3f3f3f; const LL mod = 10000; const double eps = 1e-8; struct { int to; LL w; lp(int a,LL b){to=a;w=b;} bool operator <(const lp &a)const { if(w!=a.w) return w>a.w; return to<a.to; } }; vector<lp>mp[N]; LL dis1[N],dis2[N]; int n,m; void init(){ for(int i=0;i<=n;++i)mp[i].clear(); } void dij(int s){ memset(dis1,0x3f,sizeof(dis1)); memset(dis2,0x3f,sizeof(dis2)); dis1[s]=0; priority_queue<lp>Q; Q.push(lp(s,0)); while(!Q.empty() ){ lp x=Q.top();Q.pop(); int u=x.to; if(dis2[u]<x.w)continue; for(int i=0;i<mp[u].size();++i){ lp y=mp[u][i]; if(dis2[y.to]>(x.w+y.w)){ dis2[y.to]=x.w+y.w; Q.push(lp(y.to,dis2[y.to])); } if(dis2[y.to]<dis1[y.to]){ swap(dis2[y.to],dis1[y.to]); } }
} printf("%lldn",dis2[n]); } int main(){ int t; scanf("%d",&t); while(t--){ int a,b,c; scanf("%d%d",&n,&m); init(); for(int i=0;i<m;++i){ scanf("%d%d%d",&a,&b,&c); mp[a].push_back(lp(b,c)); mp[b].push_back(lp(a,c)); } dij(1); } return 0; }
|
近期评论