Probgate	View Solution
npip99/logout
Contests
Problems
Settings
demiguo1's solution to Trolley Problem in C++1y

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

const int maxn=505;
const int maxm=2050;
const int maxk=13;
typedef long long ll;
const ll inf = 1ll<<60;
int n,k,m;
ll dp[2][maxn][maxk];
int q[maxn*maxk*20][2];
vector<pair<int, int> > edge[maxn];
int go[maxn];
ll tmp[maxk];
bool in[maxn][maxk];
void dw(ll &x, ll y) { if (y<x) x=y; }
void spfa(int t, int st) {
	for (int i=0;i<=n;i++)
		for (int j=0;j<=k;j++)
			dp[t][i][j]=inf;
	for (int j=0;j<=k;j++) dp[t][st][j]=0;
	int hd=0,tl=0;
	memset(in,0,sizeof in);
	for (int j=0;j<=k;j++) {
		in[st][j]=true;
		++tl;
		q[tl][0]=st;
		q[tl][1]=j;
	}
	while (hd!=tl) {
		int x=q[++hd][0];
		int y=q[hd][1];
		for (int i = 0; i < (int)edge[x].size(); i ++) {
			int dy = go[x]!=i;
			if (dp[t][x][y]+edge[x][i].second<dp[t][edge[x][i].first][y+dy]) {
			dp[t][edge[x][i].first][y+dy]=dp[t][x][y]+edge[x][i].second;
			int nx=edge[x][i].first;
			int ny=y+dy;
			if (!in[nx][ny]) in[nx][ny]=true,q[++tl][0]=nx,q[tl][1]=ny;
			}
		}
		in[x][y]=false;
	}
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=m;i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edge[a].push_back(make_pair(b,c));
		if (i<=n) go[a]=edge[a].size()-1;
	}
	ll ans = inf;
	spfa(0, 1);
	for (int i=1;i<=n;i++) {
		spfa(1, i);
		for (int j=0;j<=k;j++)
			tmp[j]=inf;
		for (int j=1;j<=n;j++)
			for (int t=0;t<(int)edge[j].size();t++)
				if (edge[j][t].first==i) {
					int dk = t==go[j];
					dk=1-dk;
					for (int z=0;z<=k;z++)
						dw(tmp[z+dk], dp[1][j][z]+edge[j][t].second);
				}
		for (int j=0;j<=k;j++)
			dw(ans, tmp[j]+dp[0][i][k-j]);
	}
	printf("%lld\n",ans);

	return 0;
}
Jun 18, 2016, 12:15 am EDT