pzhu 1080: 修电脑（Dijkstra 算法）

约定不等于承诺〃 2024-02-17 21:41 25阅读 0赞

### 1080: 修电脑 ###

### Description ###

孙华的笔记本电脑的适配器插头坏了，无法连通电脑充电。如果把插头换掉适配器还是可以修复的，但是现在没有直接能和适配器、电脑接口直接连通的转换器，需要使用多个转换器才能连通。

现在有n个转换器，一个转换器两头对应两种接口类型(可能相同)，一共有m种接口类型(用1,2,3...表示不同的每种接口)。适配器的接口是x，电脑的接口是y。现在在n个转换器中选几个出来连接，让适配器和电脑能够连通。但孙华为了节约钱，需要尽可能少地使用转换器，请你帮他算了一下最少要用几个转换器。

1<=n<=10^3

2<=m<=10^3

### Input ###

第一行输入n， m， x， y分别表示有n个转换器,m种接口,适配器的接口x，电脑的接口y (x≠y)

接下来的n行，每行输入x1， y1表示每个转换器两头的接口

### Output ###

用一行输出最少需要几个转换器。若随便使用多少个转换器都无法连通则输出“-1”

### Sample Input ###

5 4 1 4  
1 2  
1 3  
2 3  
3 4  
1 4  
3 4 1 4  
1 2  
1 3  
2 3

### Sample Output ###

1  
\-1

分析：最短路之Dijkstra算法

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm> 
    using namespace std;
    #define INF 100000
    const int maxn=1000+10;
    int vis[maxn];
    int g[maxn][maxn];
    int d[maxn];
    
    int main(){
    	int n,m,x,y;
    	while(scanf("%d%d%d%d",&n,&m,&x,&y)==4){
    		for(int i=1;i<=1000;i++)
    		  for(int j=1;j<=1000;j++)
    		  g[i][j]=INF;
    		  
    		for(int i=1;i<=n;i++)
    	    {
    		int x1,y1;
    		scanf("%d%d",&x1,&y1);
    		g[x1][y1]=g[y1][x1]=1;
    		}
    		
    		for(int i=1;i<=1000;i++)
    		d[i]=INF;
    		
    		d[x]=0;
    		memset(vis,0,sizeof(vis));
    		
    		for(int i=1;i<=1000;i++){
    			int j,m=INF;
    			for(int k=1;k<=1000;k++)
    			if(!vis[k] && d[k]<=m)m=d[j=k];
    			
    			vis[j]=1;
    			for(int k=1;k<=1000;k++)
    			d[k]=min(d[k],d[j]+g[j][k]);
    		}
    		
    		if(d[y]<INF)printf("%d\n",d[y]);
    		else printf("-1\n");
    	}
    	return 0;
    }