题解 P2683 【小岛】
ShineEternal
2018-07-01 15:12:44
#include<cstdio>
#include<cstring>
using namespace std;
long long dis[1001],g[101][101];
int team[10101],s,e,n,m,u,v,d,pd,head,tail;
bool exist[1001];
int hh()
{
memset(dis,0x7f,sizeof(dis));
dis[s]=0;
memset(exist,false,sizeof(exist));
team[1]=s;
head=0;
tail=1;
exist[s]=true;
do
{
head++;
u=team[head];
exist[u]=false;
for(v=1;v<=n;++v)
{
if(dis[v]>dis[u]+g[u][v])
{
dis[v]=dis[u]+g[u][v];
if(!exist[v])
{
tail++;
team[tail]=v;
exist[v]=true;
}
}
}
}while(head<tail);
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x7f,sizeof(g));
for(int i=1;i<=m;++i)
{
scanf("%d",&pd);
if(pd==1)
{
scanf("%d%d%d",&u,&v,&d);
if(d<g[u][v])
{
g[u][v]=g[v][u]=d;
}
}
else
{
scanf("%d%d",&s,&e);
hh();
if(dis[e]>=0x7f7f7f7f) printf("-1\n");
else printf("%d\n",dis[e]);
}
}
return 0;
}