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

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

• 狀態(tài)表示：f[k][i][j]表示考慮經(jīng)過前k個(gè)點(diǎn)，從i到j的距離的最小值
• 狀態(tài)計(jì)算：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"<