范沐垚


私信TA

用户名:dotcpp0614554

访问量:4473

签 名:

好大喜功

等  级
排  名 200
经  验 6481
参赛次数 0
文章发表 85
年  龄 18
在职情况 学生
学  校 看今夜 小楼灯宴
专  业 尽是良辰美眷

  自我简介:

沽名钓誉

//floyd求最短路 
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=210,INF=1e9;
int d[N][N],n,m,q;

void floyd()      //基于动态规划实现,背过 
{
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main(void)
{
	cin>>n>>m>>q;
	
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
   		    if(i==j)d[i][j]=0;   //因为存在自环,因此初始化为0,保证自环全为0 
   		    else d[i][j]=INF; 
   		    
    while(m--)
    {
    	int a,b,x;
    	cin>>a>>b>>x;
    	d[a][b]=min(d[a][b],x);	//存在重边,保留最小边 
	}
	floyd();
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(d[a][b]>INF/2)puts("impossible");
		else cout<<d[a][b]<<endl;
	}
	return 0;
 }


 

0.0分

1 人评分

  评论区