I had TL 5 because I did not add vertices to the BFS queue properly (sometimes I put the same vertex multiple times and then process in many times). You may try this test:

[test cut, too big]

Edited by moderator 06.09.2022 03:04

Check that you are dealing with an undirected graph!

You need to minimize number of visited islands firstly.

Test:
3 3
1 3
1 3 99
1 2 0
2 3 0

Answer:
2 0.99
1 3

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

int N, M, S, T, A, B, P;
int total = 0;

struct Edge {
    int to, next;
    double prob;
} edges[100010];

int head[100010];
int parent[100010], dist[100010];
double prob[100010];

void addEdge(int start, int end, int p) {
    edges[total].to = end;
    edges[total].next = head[start];
    edges[total].prob = 1.0 - (double)p / 100.0;
    head[start] = total++;
}

// The most tricky part is the probability, we are looking for the probability
// of meeting Kraken in any route so it should be P(A|B), which equals to
// P(A) + P(B) - P(AB)
int main() {
    memset(head, -1, sizeof head);
    memset(parent, -1, sizeof parent);
    memset(dist, -1, sizeof dist);
    cin >> N >> M >> S >> T;
    for (int i = 0; i <= N; i ++)
        prob[i] = 0.0;

    for (int i = 1; i <= M; i ++) {
        cin >> A >> B >> P;
        addEdge(A, B, P);
        addEdge(B, A, P);
    }

    queue<int> q;
    q.push(S);
    dist[S] = 0 ;
    prob[S] = 1.0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int idx = head[u]; idx != -1; idx = edges[idx].next) {
            int v = edges[idx].to;
            double p = edges[idx].prob;
            if (dist[v] == -1 || (dist[v] == dist[u] + 1 && prob[v] < prob[u] * p)) {
                if (dist[v] == -1) {
                    q.push(v);
                }
                dist[v] = dist[u] + 1;
                prob[v] = prob[u] * p;
                parent[v] = u;
            }
        }
    }

    vector<int> path;
    for (int i = T; i != S; i = parent[i]) {
        path.push_back(i);
    }
    path.push_back(S);
    cout << path.size() << " ";
    printf("%.7f\n", 1.0 - prob[T]);
    for (int i = path.size() - 1; i >= 1; i --)
        cout << path[i] << " ";
    cout << path[0] << endl;

    return 0;
}

Use list to make the adjacency list and not vector.

But AC with C array.

Don't use cin/cout or Scanner in java.

used dijkstra and update the probability (distance in normal dijkstra) of node v for v like below:
dis[father[v]]=dis[father[v]] + edge(father[v],v).value - dis[father[v]]*edge(father[v],v).value

is there any problem?!

I'm not good enough in probability theory...

Edited by author 15.08.2015 22:01

Both my AC submissions answer wrong (locally) on test,
which is generated by following code:

int n = (int)1e5;
printf("%d %d\n", n, n);
printf("1 %d\n", n);
printf("1 2 97\n");
printf("1 3 98\n");

for (int i = 2; i <= n - 2; i++)
   printf("%d %d %d\n", i, i + 2, 99);
printf("%d %d 98\n", n - 1, n);

To be exact, they answer
50001 1.0000000
1 2 ... n-2 n

On the other side, answer is obviously path
1 3 ... n-1 n, because probability to not meet Kraken is (4 / 100^(n/2)) for it
and (3 / 100^(n / 2)) for path 1, 2, ...

By the way, it is far from the worst test. Actually, any test like this
(with two diverging paths of same length), but where difference between products
of (1 - probability of meeting Kraken) on edges of paths is 1 and these products
are big is going to be much, much worse.

P. S. If I am misunderstanding something (for example, 10^(-6) error is allowed for
answer, not only for output (though even if it is true, it is not clear from
Russian problem statement)), then I am very sorry.

P. P. S. In hindsight it looks like statement is a bit unclear, but tests are OK
(it looks like checker does allow any path with probability to meet Kraken not more
than 10^(-6) + lowest probability), but formally, it is said in statement that path
should be optimal, just answer can be written with some error). If it is so, I
apologize for "wrong call", but I still would like to see some tweaks to statement.

Edited by author 30.07.2014 04:29

who can give some tests like test 4, pls.

how to get a 0.19 in the first test ?
what formula ?