P2683 小岛
题目背景
西伯利亚北部的寒地，坐落着由 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求最短路、、、（竟然没有TLE？！太神奇了、、、）
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define maxn 99999999
using namespace std;
bool vis[N];
queue<int>q;
int p,n,m,x,y,z,s,e,t,tot;
][];
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
struct Edge
{
int to,next;
}edge[N];
int add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
int spfa(int s)
{
while(!q.empty()) q.pop();
;i<=n;i++) vis[i]=,dis[i]=maxn;
vis[s]=;
/*while(!q.empty())
{
x=q.front();q.pop();vis[x]=false;
for(int i=head[x];i;i=edge[i].next)
{
int t=edge[i].to;
if(dis[t]>dis[x]+f[x][t])
{
dis[t]=dis[x]+f[x][t];
if(!vis[t]) vis[t]=true,q.push(t);
}
}
}*/
while(!q.empty())
{
x=q.front();q.pop();vis[x]=false;
;i<=n;i++)
{
int t=i;
if(dis[t]>dis[x]+f[x][t])
{
dis[t]=dis[x]+f[x][t];
if(!vis[t]) vis[t]=true,q.push(t);
}
}
}
}
int main()
{
n=read(),m=read();
;i<=n;i++)
;j<=n;j++)
f[i][j]=(i!=j)*maxn;
while(m--)
{
p=read();
)
{
x=read(),y=read(),z=read();
//if(f[x][y]) f[x][y]=f[y][x]=min(f[x][y],z);
//else f[x][y]=f[y][x]=z,add(x,y),add(y,x);
f[x][y]=f[y][x]=min(f[x][y],z);
}
else
{
s=read(),e=read();
spfa(s);
if(dis[e]>=maxn) printf("-1\n");
else printf("%d\n",dis[e]);
}
}
;
}