题目背景
西伯利亚北部的寒地，坐落着由 N 个小岛组成的岛屿群，我们把这些小岛依次编号为 1 到 N 。
题目描述
起初，岛屿之间没有任何的航线。后来随着交通的发展，逐渐出现了一些连通两座小岛的航线。例如增加一条在 u 号小岛与 v 号小岛之间的航线，这条航线的用时为 e。 那么沿着这条航线，u 号小岛上的人可以前往 v 号小岛，同样的 v 号小岛上的人也可以前往 u 号小岛，其中沿着这一条航线花费的时间为 e。
同时，随着旅游业的发展，越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。
输入输出格式
输入格式：
输入共 M+1 行。
第一行有两个整数 N 和 M，分别表示小岛的数与总操作数。
接下来的 M 行，每行表示一个操作，格式如下：
0 s t：表示询问从 s 号小岛到 t 号小岛的最短用时（1<=s<=n, 1<=t<=n, s\neq t）。
1 u v e：表示新增了一条从 u 号小岛到 v 号小岛，用时为 e 的双向航线（1<=u<=n, 1<=v<=n, u ≠ v, 1<=e<=10^6）。
输出格式：
输出针对每一次询问，单独输出一行。
对于每一组询问来说，如果不存在可行的道路，则输出 -1，否则输出最短用时。
输入输出样例
输入样例#1：
3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3
输出样例#1：
-1
15
12
输入样例#2：
5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3
输出样例#2：
5955
21431
9298
16392
24774
8840
说明
对于20%的数据，N<=5且M<=30。
对于40%的数据，N<=20且M<=200。
对于60%的数据，N<=80且M<=500。
对于80%的数据，N<=100且M<=2500。
对于100%的数据，N<=100且M<=5000。
思路：spfa板子。
#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 10002
using namespace std;
deque<int>que;
int n,m,s,t,tot,x;
int vis[MAXN],num[MAXN],dis[MAXN];
int to[MAXN],net[MAXN],cap[MAXN],from[MAXN];
void add(int u,int v,int w){
to[++tot]=v;net[tot]=from[u];cap[tot]=w;from[u]=tot;
}
bool spfa(int s){
for(int i=; i<=n; i++) dis[i]=;
memset(num,,sizeof(num));
memset(vis,,sizeof(vis));
while(!que.empty()) que.pop_front();
que.push_back(s);
vis[s]=;num[s]++;dis[s]=;
while(!que.empty()){
int now=que.front();
que.pop_front();vis[now]=;
for(int i=from[now]; i; i=net[i])
if(dis[to[i]]>dis[now]+cap[i]){
dis[to[i]]=dis[now]+cap[i];
if(!vis[to[i]]){
if(!que.empty()&&dis[to[i]]>dis[que.front()]) que.push_back(to[i]);
else que.push_front(to[i]);
if(++num[to[i]]>n) return false;
vis[to[i]]=;
}
}
}
return true;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d",&x);
if(x==){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
else{
scanf("%d%d",&s,&t);
int a=spfa(s);
if(dis[t]==||!a) printf("-1\n");
else printf("%d\n",dis[t]);
}
}
}