Floyd算法-创新互联
AcWing 854. Floyd求最短路
题目
文章标题:Floyd算法-创新互联
本文路径:http://scyanting.com/article/hehcp.html
https://www.acwing.com/problem/content/description/856/
给定一个n
个点m
条边的有向图,图中可能存在重边和自环,边权可能为负数。
再给定k
个询问,每个询问包含两个整数x
和y
,表示查询从点x
到点y
的最短距离,如果路径不存在,则输出impossible
。
数据保证图中不存在负权回路。
Floyd算法:动态规划的思想
- 状态表示:
f[k][i][j]
表示考虑经过前k
个点,从i
到j
的距离的最小值 - 状态计算:
f[k][i][j]=f[k-1][i][k]+f[k-1][k][j]
空间可以优化掉一维: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"<
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章标题:Floyd算法-创新互联
本文路径:http://scyanting.com/article/hehcp.html