Floyd算法-創(chuàng)新互聯(lián)

AcWing 854. Floyd求最短路 題目

https://www.acwing.com/problem/content/description/856/
給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環(huán)，邊權可能為負數(shù)。
再給定k個詢問，每個詢問包含兩個整數(shù)x和y，表示查詢從點x到點y的最短距離，如果路徑不存在，則輸出impossible。
數(shù)據(jù)保證圖中不存在負權回路。

創(chuàng)新互聯(lián)自2013年創(chuàng)立以來，先為福海等服務建站，福海等地企業(yè)，進行企業(yè)商務咨詢服務。為福海企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務解決您的所有建站問題。思路

Floyd算法：動態(tài)規(guī)劃的思想

  • 狀態(tài)表示：f[k][i][j]表示考慮經(jīng)過前k個點，從i到j的距離的最小值
  • 狀態(tài)計算：f[k][i][j]=f[k-1][i][k]+f[k-1][k][j]

空間可以優(yōu)化掉一維：f[i][j]=f[i][k]+f[k][j]

代碼
#includeusing namespace std;

typedef long long LL;

const int N=210,INF=0x3f3f3f3f;
int d[N][N];
int n,m,t;

int main()
{cin>>n>>m>>t;
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=n;i++) d[i][i]=0;

	while(m--)
	{int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=min(d[a][b],c);
	}
    //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]);

	while(t--)
	{int x,y;
		cin>>x>>y;
		if(d[x][y]>INF/2) cout<<"impossible"<

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：Floyd算法-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://muchs.cn/article28/hehcp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、關鍵詞優(yōu)化、外貿(mào)建站、App開發(fā)、用戶體驗、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)