2015
04-10

# Ideal Path

New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colored into some color ci. Visitors of the labyrinth are dropped from the helicopter to the room number 1 and their goal is to get to the labyrinth exit located in the room number n.
Labyrinth owners are planning to run a contest tomorrow. Several runners will be dropped to the room number 1. They will run to the room number n writing down colors of passages as they run through them. The contestant with the shortest sequence of colors is the winner of the contest. If there are several contestants with the same sequence length, the one with the ideal path is the winner. The path is the ideal path if its color sequence is the lexicographically smallest among shortest paths.
Andrew is preparing for the contest. He took a helicopter tour above New Lostland and made a picture of the labyrinth. Your task is to help him find the ideal path from the room number 1 to the room number n that would allow him to win the contest.
Note
A sequence (a1, a2, …, ak) is lexicographically smaller than a sequence (b1, b2, …, bk) if there exists i such that ai < bi, and aj = bj for all j < i.

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains integers n and m – the number of rooms and passages, respectively (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). The following m lines describe passages, each passage is described with three integer numbers: ai, bi, and ci – the numbers of rooms it connects and its color (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109). Each passage can be passed in either direction. Two rooms can be connected with more than one passage, there can be a passage from a room to itself. It is guaranteed that it is possible to reach the room number n from the room number 1.

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains integers n and m – the number of rooms and passages, respectively (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000). The following m lines describe passages, each passage is described with three integer numbers: ai, bi, and ci – the numbers of rooms it connects and its color (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109). Each passage can be passed in either direction. Two rooms can be connected with more than one passage, there can be a passage from a room to itself. It is guaranteed that it is possible to reach the room number n from the room number 1.

1
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

2
1 3

// 这题我用的解法是3次BFS，前两次BFS分别从起点开始搜索和从终点开始搜索。
// 这样就求出了每个点到起点和到终点的最短距离。假设某点x，它到起点的最短
// 距离加上它到终点的最短距离等于起点到终点的最短距离，即
// sdis[x] + edis[x] == len。则证明x是最短路径上的一个点。最后一次
#include <iostream>
using namespace std;
const int maxn = 100005;
const int maxm = 400005;
const int inf  = 1000000005;
int head[maxn], vert[maxm], colo[maxm], noxt[maxm], cunt;
int sdis[maxn], edis[maxn], path[maxn], leng;
bool vis[maxn], rit[maxn];
void init(int n)
{
cunt = 0;
for (int i = 0; i <= n; i++)
{
sdis[i] = -1;
edis[i] = -1;
vis[i] = 0;
rit[i] = 0;
path[i] = inf;
}
}
void addedge(int x, int y, int c)
{
vert[cunt] = y;
colo[cunt] = c;
}
void BFS(int start, int *dis)
{
dis[start] = 0;
queue[qtail++] = start;
{
for (int p = head[x]; p != -1; p = noxt[p])
{
int y = vert[p];
if (-1 == dis[y])
{
dis[y] = dis[x] + 1;
queue[qtail++] = y;
}
}
}
}
{
queue[qtail++] = 1;
int step = 0;
{
int ttail = qtail;
{
for (int p = head[x]; p != -1; p = noxt[p])
{
int y = vert[p];
int c = colo[p];
if (rit[y] && sdis[y] == step + 1)
{
if (c < path[step])
{
path[step] = c;
for (int i = ttail; i < qtail; i++)
vis[queue[i]] = 0;
qtail = ttail;
vis[y] = 1;
queue[qtail++] = y;
}
else if (c == path[step] && !vis[y])
{
vis[y] = 1;
queue[qtail++] = y;
}
}
}
}
step++;
}
}
int main()
{
int test, cas;
int n, m, a, b, c;
scanf("%d", &test);
for (cas = 1; cas <= test; cas++)
{
scanf("%d %d", &n, &m);
init(n);
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &a, &b, &c);
if (a == b) continue;
}
BFS(1, sdis);
BFS(n, edis);
leng = sdis[n];
for (int i = 1; i <= n; i++)
{
if (sdis[i] + edis[i] == leng)
rit[i] = 1;
}
printf("%d/n", leng);
for (int i = 0; i < leng; i++)
{
if (i) printf(" ");
printf("%d", path[i]);
}
printf("/n");
}
return 0;
}



1. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count