CODEFORCES ROUND #374 (DIV. 2) C
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
const int INF = 0x3f3f3f3f;
const int QSIZE = 2000000;
using namespace std;
typedef struct Edge
{
int end, len;
Edge *next;
} * lpEdge;
int F[5001][5001]; ///F[v][j] = min{F[u][j - 1] + t[u][v}
bool B[5001][5001];
int QUEX[2000000];
int QUEY[2000000];
lpEdge V[5001];
lpEdge E[5001];
int n, m, T;
void bfs()
{
int head, tail;
head = tail = 0;
QUEX[tail] = 1;
QUEY[tail++] = 1;
B[1][1] = true;
while (head != tail)
{
int i = QUEX[head];
int j = QUEY[head++];
B[i][j] = false;
if (head >= QSIZE)
head -= QSIZE;
for (Edge *p = V[i]; p; p = p->next)
{
if (F[i][j] + p->len < F[p->end][j + 1])
{
F[p->end][j + 1] = F[i][j] + p->len;
if (!B[p->end][j + 1])
{
B[p->end][j + 1] = true;
QUEX[tail] = p->end;
QUEY[tail++] = j + 1;
if (tail >= QSIZE)
tail -= QSIZE;
}
}
}
}
}
void print(int i, int t, int k)
{
for (Edge *p = E[i]; p; p = p->next)
{
if (t - p->len == F[p->end][k - 1])
{
print(p->end, t - p->len, k - 1);
break;
}
}
printf("%d ", i);
}
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 0, u, v, w; i != m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
Edge *tmp = new Edge();
tmp->end = v;
tmp->len = w;
tmp->next = V[u];
V[u] = tmp;
tmp = new Edge();
tmp->end = u;
tmp->len = w;
tmp->next = E[v];
E[v] = tmp;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
F[i][j] = INF;
F[1][1] = 0;
bfs();
for (int i = n; i >= 2; --i)
if (F[n][i] <= T)
{
printf("%d\n", i);
print(n, F[n][i], i);
break;
}
return 0;
}