描述
西伯利亚北部的寒地，坐落着由 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，否则输出最短用时。
裸上SPFA
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; struct na{
int y,z,ne;
na(){
ne=;
}
};
int n,m,dis[][],c,x,y,z,p,l[],r[],num=,k;
na b[];
char o;
queue <int> q;
bool bo[];
const int INF=1e9;
inline int read(){
p=;o=getchar();
while(o<''||o>'') o=getchar();
while(o>=''&&o<='') p=p*+o-,o=getchar();
return p;
}
inline void in(int x,int y,int z){
num++;
if (l[x]==) l[x]=num;else b[r[x]].ne=num;
b[num].y=y;b[num].z=z;r[x]=num;
}
int main(){
n=read();m=read();
int i,j;
for (i=;i<=n;i++)
for (j=;j<=n;j++) dis[i][j]=INF;
for (i=;i<=n;i++) dis[i][i]=;
while(m--){
c=read();x=read();y=read();
if (c==){
if (dis[x][y]==INF) printf("-1\n");else printf("%d\n",dis[x][y]);
}else{
z=read();
in(x,y,z);in(y,x,z);
for (i=;i<=n;i++){
q.push(x);q.push(y);
bo[x]=bo[y]=;
while(!q.empty()){
k=q.front();q.pop();
bo[k]=;
for (j=l[k];j;j=b[j].ne)
if (dis[i][b[j].y]>dis[i][k]+b[j].z){
dis[i][b[j].y]=dis[i][k]+b[j].z;
if (!bo[b[j].y])q.push(b[j].y),bo[b[j].y]=;
}
}
}
}
}
}