Vijos 1942-小岛【最小生成树】

今天药忘吃喽~ 2022-08-20 03:13 42阅读 0赞

**1942**小岛

[Accepted][]

标签： [安徽2015][2015] \[显示标签\]

## 描述 ##

西伯利亚北部的寒地，坐落着由 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 ##

### 样例输入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 ##

### 样例输入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。

## 来源 ##

AHOI 2015

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    int map[200][200];
    int dis[200];
    bool vis[200];
    int n,m;
    int prim(int x,int y)
    {
    	int i,j;
    	memset(vis,false,sizeof(vis));
    	for(i=1;i<=n;i++)
    	{
    		dis[i]=map[x][i];
    	}
    	vis[i]=true;
    	dis[x]=0;
    	for(i=1;i<=n-1;i++)
    	{
    		int pos=x,min=INF;
    		for(j=1;j<=n;j++)
    		{
    			if(!vis[j]&&dis[j]<min)
    			{
    				pos=j;
    				min=dis[j];
    			}
    		}
    		vis[pos]=true;
    		for(j=1;j<=n;j++)
    		{
    			if(!vis[j]&&dis[j]>dis[pos]+map[pos][j])
    			{
    				dis[j]=dis[pos]+map[pos][j];
    			}
    		}
    	}
    	return dis[y]==INF?-1:dis[y];
    }
    int main()
    {
    	scanf("%d%d",&n,&m);
    		int i,j;
    		memset(map,INF,sizeof(map));
    		for(i=1;i<=m;i++)
    		{
    			int p;
    			scanf("%d",&p);
    			if(p==1)
    			{
    				int xx,yy,t;
    				scanf("%d%d%d",&xx,&yy,&t);
    				if(t<map[xx][yy])
    				{
    					map[xx][yy]=t;
    					map[yy][xx]=t;
    				}
    			}
    			if(p==0)
    			{
    				int uu,ui;
    				scanf("%d%d",&uu,&ui);
    				int yy=prim(uu,ui);
    				if(yy==-1)
    				printf("-1\n");
    				else
    				printf("%d\n",yy);
    			}
    		}
    	return 0;
    }

[Accepted]: https://vijos.org/records/56a8270117f3cad805292933
[2015]: https://vijos.org/p/%E7%9C%81%E9%80%89+%E5%AE%89%E5%BE%BD+2015