Skip to content

Instantly share code, notes, and snippets.

@Ghastlcon Ghastlcon/park.cpp

Created Dec 9, 2017
Embed
What would you like to do?
park
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <utility>
#define N 100020
#define M 200020
#define K 55
#define INFINITE 999999999
using namespace std;
typedef struct
{
int u;
int v;
int w;
}EDGE;
EDGE a[M];
int h[N], v[M], w[M], t[M], c;
namespace Shortest
{
int d[N], k;
bool u[N];
pair<int, int> f[N * 4];
void BuildWinner(int n)
{
int i;
k = pow(2, ceil(log(n) / log(2)));
for(i = 0;i < n;i ++)
f[i + k] = make_pair(INFINITE, i);
for(i = n + k;i < k * 2;i ++)
f[i] = make_pair(INFINITE, -1);
for(i = k - 1;i > 0;i --)
{
f[i].first = min(f[i << 1].first, f[i << 1 | 1].first);
f[i].second = f[i << 1].first < f[i << 1 | 1].first ? f[i << 1].second : f[i << 1 | 1].second;
}
return;
}
void SetWinner(int p, int v)
{
for(f[p += k].first = v;p >>= 1;)
{
f[p].first = min(f[p << 1].first, f[p << 1 | 1].first);
f[p].second = f[p << 1].first < f[p << 1 | 1].first ? f[p << 1].second : f[p << 1 | 1].second;
}
return;
}
void Dijkstra(int s, int n)
{
int i, j;
pair<int, int> p;
BuildWinner(n);
SetWinner(s, 0);
fill(d, d + n, INFINITE);
memset(u, false, sizeof(u));
u[s] = true;
d[s] = 0;
for(i = 1;i < n;i ++)
{
p = f[1];
if(p.second == -1)
break;
u[p.second] = true;
SetWinner(p.second, INFINITE);
for(j = h[p.second];j != -1;j = t[j])
if(!u[v[j]] && d[v[j]] > p.first + w[j])
{
d[v[j]] = p.first + w[j];
SetWinner(v[j], p.first + w[j]);
}
}
return;
}
}
namespace Topo
{
int f[N], g[N];
int u[N], o[N], b;
bool Topo(int x, int c, int n, int k)
{
int i;
bool r;
//printf("fetch %d\n", x);
if(u[x] != -1)
{
//printf("CHECK %d(%d, %d)\n", x, c, u[x]);
return u[x] == c && f[x] + g[x] <= f[n - 1] + k;
}
u[x] = c;
for(i = h[x], r = false;i != -1;i = t[i])
r |= Topo(v[i], c, n, k);
o[x] = b ++;
return r;
}
}
namespace Countpath
{
int f[N], s[N];
int g[N], r[N][K];
bool Compare(int a, int b)
{
return f[a] == f[b] ? s[a] > s[b] : f[a] < f[b];
}
int Solve(int n, int s, int t, int k, int p)
{
int i, j, e;
memset(r, 0, sizeof(r));
for(i = 0;i < n;i ++)
g[i] = i;
sort(g, g + n, Compare);
r[s][0] = 1;
for(i = 0;i <= k;i ++)
for(j = 0;j < n;j ++)
for(e = h[g[j]];e != -1;e = ::t[e])
if(f[g[j]] + i + w[e] <= f[v[e]] + k)
(r[v[e]][f[g[j]] + i + w[e] - f[v[e]]] += r[g[j]][i]) %= p;
for(i = j = 0;i <= k;i ++)
(j += r[t][i]) %= p;
return j;
}
}
int Scan(void)
{
int s;
char c;
for(s = 0;(c = getchar()) != EOF && !isdigit(c);)
;
do
s = s * 10 + c - 48;
while((c = getchar()) != EOF && isdigit(c));
return s;
}
void AddEdge(int u, int v, int w)
{
::v[c] = v;
::w[c] = w;
t[c] = h[u];
h[u] = c ++;
return;
}
void InitEdge(void)
{
c = 0;
memset(h, -1, sizeof(h));
return;
}
void Solve(void)
{
int n, m, k, p;
int i;
n = Scan();
m = Scan();
k = Scan();
p = Scan();
InitEdge();
for(i = 0;i < m;i ++)
{
a[i].u = Scan();
a[i].v = Scan();
a[i].w = Scan();
AddEdge(-- a[i].u, -- a[i].v, a[i].w);
}
Shortest::Dijkstra( 0, n);
memcpy(Topo ::f, Shortest::d, sizeof(int) * n);
memcpy(Countpath::f, Shortest::d, sizeof(int) * n);
InitEdge();
for(i = 0;i < m;i ++)
AddEdge(a[i].v, a[i].u, a[i].w);
Shortest::Dijkstra(n - 1, n);
memcpy(Topo ::g, Shortest::d, sizeof(int) * n);
/*for(i=0;i<n;i++)
cout<<Topo::f[i]<<' ';puts("");
for(i=0;i<n;i++)
cout<<Topo::g[i]<<' ';puts("");*/
InitEdge();
for(i = 0;i < m;i ++)
if(!a[i].w)
{
//printf("%d -> %d\n", a[i].u, a[i].v);
AddEdge(a[i].u, a[i].v, a[i].w);
}
memset(Topo::u, -1, sizeof(Topo::u));
Topo::b = 0;
/*printf("%d\n", h[14]);
cout<<Topo::Topo(14,14,n,k)<<endl;*/
for(i = 0;i < n;i ++)
{
//printf("%d\n",Topo::u[i]);
if(Topo::u[i] == -1 && Topo::Topo(i, i, n, k))
{
printf("-1\n");
return;
}
}
memcpy(Countpath::s, Topo ::o, sizeof(int) * n);
/*for(i=0;i<n;i++)
cout<<Topo::o[i]<<' ';puts("");*/
InitEdge();
for(i = 0;i < m;i ++)
AddEdge(a[i].u, a[i].v, a[i].w);
printf("%d\n", Countpath::Solve(n, 0, n - 1, k, p));
return;
}
int main() //park.cpp
{
int t;
freopen("park.in" , "r", stdin );
freopen("park.out", "w", stdout);
t = Scan();
while(t --)
Solve();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.