首页 > 代码库 > 【Heap-dijkstra】Gym - 100923B - Por Costel and the Algorithm

【Heap-dijkstra】Gym - 100923B - Por Costel and the Algorithm

algoritm.in / algoritm.out

Even though he isn‘t a student of computer science, Por Costel the pig has started to study Graph Theory. Today he‘s learning about Bellman-Ford, an algorithm that calculates the minimum cost path from a source node (for instance, node 1) to all the other nodes in a directed graph with weighted edges. Por Costel, utilizing his scarce programming knowledge has managed to scramble the following code in C++, a variation of the Bellman-Ford algorithm:

技术分享

You can notice a lot of deficiencies in the above code. In addition to its rudimentary documentation, we can see that Por Costel has stored this graph as an array of edges (the array 技术分享). An edge is stored as the triplet 技术分享 signifying an edge that spans from 技术分享 to 技术分享 and has weight 技术分享. But even worse is the fact that the algorithm is SLOW!

As we want our hooved friend to walk away with a good impression about computer science, we want his code to execute as FAST as possible. In order to do so, we can modify the order of edges in the array 技术分享 so that the while loop executes a small number of times.

Given a directed graph of 技术分享 nodes and 技术分享 edges, you are asked to produce an ordering of the edges such that the Bellman-Ford algorithm written by Por Costel should finish after at most two iterations of the while loop(that is, the program should enter the while loop at most twice).

Input

The first line of the file algoritm.in will contain an integer 技术分享 技术分享, the number of test cases.

Each of the 技术分享 test cases has the following format: on the first line, there are two numbers 技术分享 and 技术分享 (技术分享), the number of nodes and the number of edges in the graph respectively.

The next 技术分享 lines describe the edges, each containing three integers 技术分享 signifying there is an edge from node 技术分享 to node 技术分享 with weight 技术分享 (技术分享)

It is guaranteed that node 技术分享 has at least one outgoing edge.

The graph may contain self loops and/or multiple edges.

Output

The output file algoritm.out should contain 技术分享 lines representing the answers to each test case.

For each test case you should output a permutation of numbers from 技术分享 to 技术分享, representing the order of the edges you want in Por Costel‘s array of edges 技术分享.

The edges are considered indexed by the order in which they are given in the input (the 技术分享-th edge read is the edge with index 技术分享).

If there are multiple solutions, you are allowed to print any of them.

Example

Input
1
4 4
1 2 1
3 4 2
2 3 3
1 3 1
Output
1 4 2 3

 

题意就是一个傻逼写了个最短路,问你怎么将输入的graph的边排序,使得他的最短路只跑一次。

显然先跑在最短路径树上的边,再跑其他的边,就只需要一次了。

必须用堆dijkstra,好像卡了spfa。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
#define INF 1000000000007ll
#define N 100010
#define M 200010
struct Point{ll d;int u;
Point(const ll &X,const int &Y){d=X;u=Y;}
Point(){}};
int T,n,m;
int cnt;
bool operator < (Point a,Point b){return a.d>b.d;}
priority_queue<Point>q;
int v[M],__next[M],first[N],w[M],e;
int fa[N],fam[N];
ll d[N];
void AddEdge(int U,int V,int W)
{
	v[++e]=V;
	w[e]=W;
	__next[e]=first[U];
	first[U]=e;
}
bool vis[N],intree[M];
void dijkstra(int S)
{
    for(int i=1;i<=n;++i) d[i]=INF;
    d[S]=0; q.push(Point(0,S));
    while(!q.empty())
      {
        Point x=q.top(); q.pop();
        if(!vis[x.u])
          {
            vis[x.u]=1;
            for(int i=first[x.u];i;i=__next[i])
              if(d[v[i]]>d[x.u]+(ll)w[i])
                {
                  d[v[i]]=d[x.u]+(ll)w[i];
                  fa[v[i]]=x.u;
                  intree[fam[v[i]]]=0;
                  fam[v[i]]=i;
                  intree[i]=1;
                  q.push(Point(d[v[i]],v[i]));
                }
          }
      }
}
void dfs(int U)
{
	for(int i=first[U];i;i=__next[i])
	  if(intree[i])
	    {
	      ++cnt;
	      printf("%d%c",i,cnt==m ? ‘\n‘ : ‘ ‘);
	      dfs(v[i]);
	    }
}
int main()
{
	freopen("algoritm.in","r",stdin);
	freopen("algoritm.out","w",stdout);
	//freopen("b.in","r",stdin);
	int x,y,z;
	scanf("%d",&T);
	for(;T;--T)
	  {
	  	cnt=e=0;
	  	memset(v,0,sizeof(v));
	  	memset(w,0,sizeof(w));
	  	memset(__next,0,sizeof(__next));
	  	memset(first,0,sizeof(first));
	  	memset(fa,0,sizeof(fa));
	  	memset(fam,0,sizeof(fam));
	  	memset(d,0,sizeof(d));
	  	memset(vis,0,sizeof(vis));
	  	memset(intree,0,sizeof(intree));
	  	scanf("%d%d",&n,&m);
	  	for(int i=1;i<=m;++i)
	  	  {
	  	  	scanf("%d%d%d",&x,&y,&z);
	  	  	AddEdge(x,y,z);
	  	  }
	  	dijkstra(1);
	  	dfs(1);
	  	for(int i=1;i<=m;++i)
	  	  if(!intree[i])
	  	    {
	  	      ++cnt;
	  	      printf("%d%c",i,cnt==m ? ‘\n‘ : ‘ ‘);
	  	    }
	  }
	return 0;
}

【Heap-dijkstra】Gym - 100923B - Por Costel and the Algorithm