codeforce Gym 100342H Hard Test （思考题）

题意：构造让Dijkstra单源最短路算法有效松弛次数最多的数据。。。

题解：构造，题意换种说法就是更新晚的路径要比更新早的路径短。因为所有点都会更新一次，那么按照更新时间形成一条链，即到最后一个点的最短路径，

注意：越在这条链的后面的边越晚更新，然后添加边，在前面的点所连的边一定是先更新的，所以反过来添加边的时候只要保证比之前的路径更长就行了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define bug(x) cout<<#x<<'='<<x<<endl;

#define FOR(i,s,e) for(int i = s; i < e; i++)

const int maxn = ;

int G[maxn][maxn];

#define local

int main()

{

#ifdef local

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

#endif // local

    //memset(G,-1,sizeof(G));

    int n,m; scanf("%d%d",&n,&m);for(int i = ; i < n; i ++) {

        printf("%d %d 0\n",i,i+);

    }

    m -= n-;

    for(int i = n-; i >  && m; i--){

        for(int j = i+; j <= n && m; j++){

            m--;

            G[i][j] = G[i][i+] + G[i+][j];

            printf("%d %d %d\n",i,j,++G[i][j]);

        }

    }

    return ;

}

巴特西

codeforce Gym 100342H Hard Test （思考题）

最新文章

热门文章