题目描述

blablabla

样例

#include <iostream>
#include <cstring>
using namespace std;
const int N=510,M=10010;
int dist[N],last[N];
int n,m,k;
struct node{
    int a,b,c;
}edge[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)//思路重点在于此处，m条边都遍历k次，如果dist[b]大于dist[a]+c，就更新它的值，值得注意的是需要备份
    {
        memcpy(last,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            auto s=edge[j];
            if(dist[s.b]>last[s.a]+s.c) dist[s.b]=last[s.a]+s.c;
        }
    }
    return dist[n];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};

    }
   int t= bellman_ford();
   if(t>0x3f3f3f3f/2) cout<<"impossible";
   else     cout<<t;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla