HDU 4889

Scary Path Finding Algorithm

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 268 Accepted Submission(s): 121 Special Judge

Problem Description

Fackyyj loves the challenge phase in TwosigmaCrap(TC). One day, he meet a task asking him to find shortest path from vertex 1 to vertex n, in a graph with at most n vertices and m edges. (1 ≤ n ≤ 100,0 ≤ m ≤ n(n-1))Fackyyj solved this problem at first glance, after that he opened someone’s submission, spotted the following code: long long spfa_slf() { int n,m; cin >> n >> m; vector<pair<int,int> > edges[111]; for(int i = 0;i < m;i++) { int x,y,w; cin >> x >> y >> w; edges[x].push_back(make_pair(y,w)); } deque q; vector dist(n+1, ~0ULL>>1); vector inQueue(n+1, false); dist[1] = 0; q.push_back(1); inQueue[1] = true; int doge = 0; while(!q.empty()) { int x = q.front(); q.pop_front(); if(doge++ > C) { puts(“doge”); return 233; } for(vector<pair<int,int> >::iterator it = edges[x].begin(); it != edges[x].end();++it) { int y = it->first; int w = it->second; if(dist[y] > dist[x] + w) { dist[y] = dist[x] + w; if(!inQueue[y]) { inQueue[y] = true; if(!q.empty() && dist[y] > dist[q.front()]) q.push_back(y); else q.push_front(y); } } } inQueue[x] = false; } return dist[n]; } Fackyyj’s face lit up with an evil smile. He immediately clicked button “Challenge!”, but due to a hard disk failure, all of his test case generators were lost! Fackyyj had no interest on recreating his precise generators, so he asked you to write one. The generator should be able to generate a test case with at most 100 vertices, and it must be able to fail the above code, i.e. let the above code print “doge”. It should NOT contain any negative-cost loop. For those guys who doesn’t know C++, Fackyyj explain the general idea of the above algorithm by the following psuedo-code:

Input

Input contains several test cases, please process till EOF. For each test case, there will be a single line containing an integer C. It is the constant C in the above code. (C <= 23333333)

Output

For each test case, on the first line, print two integers, n and m, indicating the number of vertices and the number of edges of your graph. Next m lines, on each line print x y w, means there is a road from x to y, cost w. 1 ≤ n ≤ 100,0 ≤ m ≤ n(n-1),|w| < 231. Note that your output shouldn’t contain any negative-cost loop.

Sample Input

Sample Output

4 3 1 2 1 2 3 1 3 4 1

Author

Fudan University

Source

2014 Multi-University Training Contest 3

直接进行构造。

/* ***************

Author        :kuangbin

Created Time  :2014/8/3 12:18:25

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校3\HDU4889.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int C;

	while(scanf("%d",&C) == 1)

	{

		int n = 30;

		int m = n*(n-1)/2;

		printf("%d %d\n",n,m);

		for(int i = 1;i <= n;i++)

		{

			for(int j = i+1;j <= n;j++)

				printf("%d %d %d\n",i,j,-(1<<(n-i)));

		}

	}

    return 0;

}