P2683 小岛
spfa，
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define maxn 1000000 4 #define inf 1<<30 5 #define LL long long 6 int n,m,s,num,t,head[maxn],dis[maxn],if_; 7 struct Edge{ 8 int v,d,next; 9 }edge[maxn]; 10 11 void ins(int u,int v,int d) 12 { 13 edge[++num].v=v; 14 edge[num].d=d; 15 edge[num].next=head[u]; 16 head[u]=num; 17 } 18 19 void spfa(int s) 20 { 21 queue<int>que; 22 bool vis[maxn]; 23 memset(vis,false,sizeof(vis)); 24 for(int i=1;i<=n;i++) dis[i]=inf; 25 dis[s]=0; vis[s]=1; 26 que.push(s); 27 while(!que.empty()) 28 { 29 int cur=que.front(); 30 que.pop(); 31 for(int i=head[cur];i;i=edge[i].next) 32 { 33 if(dis[cur]+edge[i].d<dis[edge[i].v]) 34 { 35 dis[edge[i].v]=dis[cur]+edge[i].d; 36 if(!vis[edge[i].v]) 37 { 38 vis[edge[i].v]=1; 39 que.push(edge[i].v); 40 } 41 } 42 } 43 vis[cur]=false; 44 } 45 } 46 47 int main() 48 { 49 scanf("%d%d",&n,&m); 50 for(int i=1;i<=m;i++) 51 { 52 int u,v,d; 53 scanf("%d",&if_); 54 if(if_==1) 55 { 56 scanf("%d%d%d",&u,&v,&d); 57 ins(u,v,d); ins(v,u,d); 58 } 59 else{ 60 scanf("%d%d",&s,&t); 61 spfa(s); 62 printf("%d ",dis[t]==inf?-1:dis[t]); 63 } 64 } 65 return 0; 66 }