185. Two shortest

time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Yesterday Vasya and Petya quarreled badly, and now they don't want to see each other on their way to school. The problem is that they live in one and the same house, leave the house at the same time and go at the same speed by the shortest road. Neither of them wants to change their principles, that is why they want to find two separate shortest routes, which won't make them go along one road, but still they can meet at any junction. They ask you to help them. They number all the junctions with numbers from 1 to N (home and school are also considered as junctions). So their house has the number 1 and the school has the number N, each road connects two junctions exactly, and there cannot be several roads between any two junctions.

Input
The first line contains two integer numbers N and M (2<=N<=400), where M is the number of roads Petya and Vasya noticed. Each of the following M lines contains 3 integers: X, Y and L (1<=X, Y<=N, 1<=L<=10000), where X and Y - numbers of junctions, connected by the road and L is the length of the road.

Output
Write to the first line numbers of the junctions in the way they passed them on the first route. Write to the second line numbers of the junctions in the way they passed them on the second route. If it is impossible to help guys, then output "No solution".

Sample test(s)

Input
6 8
1 2 1
3 2 1
3 4 1
1 3 2
4 2 2
4 5 1
5 6 1
4 6 2

Output
1 3 4 5 6
1 2 4 6

题意：两个人都从1->n中间的边不可以重复，点可以重复，求是否存在方案，并输出两个人的路径

做法：我最开始的想法是正确的，根据hdu5294Tricks Device【最短路+网络流】的做法，就是跑两遍spfa找出在最短路上的边加入网络流的构图中。问题是怎么输出，其实就dfs就可以啊，flow==0且是原边的就继续往下走，走过一条边就标记下次不走，标记也不用新开数组，flow=-1即可

内存卡的有病啊，连数组多大都不给，找到的Ac代码都是卡着内存过的，懒得改了==

据说这个题有费用流的做法，百思不得其解

p.s.下午又做题的原因主要是1点整的时候我正和周公约会，被旁边的说话声吵醒……妈蛋，吓死宝宝了有木有 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN = 410;
const int MAXM = 260100;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int to, next, cap;
};

Edge edge[MAXM];
int level[MAXN];
int head[MAXN];
int dist[MAXN];
int map[MAXN][MAXN];
int src, des, cnt, flag;

void SPFA(int n)
{
	int inqueue[MAXN];
	memset( dist, INF, sizeof dist );
	memset( inqueue, 0, sizeof inqueue );
	dist[1] = 0;	
	deque<int> dq;
	dq.push_back( 1 );
	inqueue[1] = 1;

	while(!dq.empty())
	{
		int next = dq.front();
		dq.pop_front();
		inqueue[next] = 0;
		for(int i = 1; i <= n; i++)
		{
			if(dist[i] > dist[next] + map[next][i])
			{
				dist[i] = dist[next] + map[next][i];
				if(!inqueue[i])
				{
					if(!dq.empty() && dist[i] > dist[dq.front()])
						dq.push_front( i );
					else
						dq.push_back( i );
				}
			}
		}
	}
}

void addedge( int from, int to, int cap )
{
	edge[cnt].to = to;
	edge[cnt].cap = cap;
	edge[cnt].next = head[from];
	head[from] = cnt++;

	swap( from, to );

	edge[cnt].to = to;
	edge[cnt].cap = 0;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}

int bfs()
{
	memset( level, -1, sizeof level );
	cnt = 0;
	queue<int> q;
	while (!q.empty())
		q.pop();
	level[src] = 0;
	q.push( src );

	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if (edge[i].cap > 0 && level[v] == -1)
			{
				level[v] = level[u] + 1;
				q.push( v );
			}
		}
	}
	return level[des] != -1;
}

int dfs( int u, int f )
{
	if (u == des) return f;
	int tem;

	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		if (edge[i].cap > 0 && level[v] == level[u] + 1)
		{
			tem = dfs( v, min( f, edge[i].cap ) );
			if (tem > 0)
			{
				edge[i].cap -= tem;
				edge[i^1].cap += tem;
				return tem;
			}
		}
	}
	level[u] = -1;
	return 0;
}

int Dinic()
{
	int ans = 0, tem;
	while (bfs())
	{
		while ((tem = dfs( src, INF )) > 0)
		{
			ans += tem;
		}
	}
	return ans;
}

void print( int n, int u )
{
	if(u != n)
	{
		printf( "%d ", u );
	}
	else
	{
		printf( "%d\n", u );
		flag = true;
		return;
	}

	for(int i = head[u]; i != -1&&!flag; i = edge[i].next)
	{
		int v = edge[i].to;
		if(edge[i].cap == 0 && i % 2 == 0)
		{
			edge[i].cap = -1;
			print( n, v );
		}
	}
}

int main()
{
	int n,m;
	while(cin >> n >> m)
	{
		src = 1, des = n;
		memset( head, -1, sizeof head );
		memset( map, INF, sizeof map );
		for(int i = 1; i <= n; i++)
			map[i][i] = 0;
		cnt = 0;

		int a, b, c;
		for(int i = 1; i <= m; i++)
		{
			cin >> a >> b >> c;
			map[a][b] = map[b][a] = c;
		}
		SPFA( n );

		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(dist[i] + map[i][j] == dist[j])
				{
					addedge( i, j, 1 );
				}
			}
		}
		int ans = Dinic();
		if(ans < 2)
			cout << "No solution" << endl;
		else
		{
			print( n,src );
			flag = false;
			print( n, src );
		}
	}
	return 0;
}