Black Spot
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Bootstrap: Jones's terrible leviathan will find you and drag the Pearl back to the depths and you along with it.
Jack: Any idea when Jones might release said terrible beastie?
Bootstrap: I already told you, Jack. Your time is up. It comes now,
drawn with ravenous hunger to the man what bears the black spot.
Jack: Any idea when Jones might release said terrible beastie?
Bootstrap: I already told you, Jack. Your time is up. It comes now,
drawn with ravenous hunger to the man what bears the black spot.
Captain Jack Sparrow has got a black spot on his hand and
he avoids going to high seas because sea monster Kraken
is waiting there for him. But he can’t stay in his place due
to his freedom-loving nature. And now Jack is going to Tortuga.
he avoids going to high seas because sea monster Kraken
is waiting there for him. But he can’t stay in his place due
to his freedom-loving nature. And now Jack is going to Tortuga.
There are n islands in the Caribbean Sea. Jack is going to reach Tortuga,
sailing from island to island by routes that allow him to be
in the high seas for a short time.
Jack knows such routes for some pairs of islands,
but they could also be dangerous for him.
There is a probability to meet Kraken on each route.
sailing from island to island by routes that allow him to be
in the high seas for a short time.
Jack knows such routes for some pairs of islands,
but they could also be dangerous for him.
There is a probability to meet Kraken on each route.
Jack is in a hurry and he wants to reach Tortuga visiting as
small number of islands as possible.
If there are several variants of such paths he wants to
choose a path with the least probability of meeting Kraken.
But Jack will be satisfied with any path with minimal number of islands if the probability
of meeting Kraken on this path differs from the minimal one in no more than 10−6.
Help Jack find such path.
small number of islands as possible.
If there are several variants of such paths he wants to
choose a path with the least probability of meeting Kraken.
But Jack will be satisfied with any path with minimal number of islands if the probability
of meeting Kraken on this path differs from the minimal one in no more than 10−6.
Help Jack find such path.
Input
The first line contains two integers n, m — the quantity of islands
and known routes between them (2 ≤ n ≤ 105; 1 ≤ m ≤ 105).
The second line contains two integers s and t —
the number of island where Jack is and the number of Tortuga (1 ≤ s, t ≤ n; s ≠ t).
Each of the following m lines contains three integers —
the numbers of islands ai and bi where the route is known and pi —
probability to meet Kraken on that route as percentage (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ pi ≤ 99).
No more than one route is known between each pair of islands.
and known routes between them (2 ≤ n ≤ 105; 1 ≤ m ≤ 105).
The second line contains two integers s and t —
the number of island where Jack is and the number of Tortuga (1 ≤ s, t ≤ n; s ≠ t).
Each of the following m lines contains three integers —
the numbers of islands ai and bi where the route is known and pi —
probability to meet Kraken on that route as percentage (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ pi ≤ 99).
No more than one route is known between each pair of islands.
Output
In the first line output k — number of islands along the
path and p — probability to meet Kraken on that path.
An absolute error of p should be up to 10−6.
In the next line output k integers — numbers of islands in the order of the path.
If there are several solutions, output any of them.
path and p — probability to meet Kraken on that path.
An absolute error of p should be up to 10−6.
In the next line output k integers — numbers of islands in the order of the path.
If there are several solutions, output any of them.
Sample
| input | output |
|---|---|
4 4 |
3 0.19 |
Problem Author: Denis Dublennykh (prepared by Egor Shchelkonogov)
【分析】就是个最短路。题目要求遇见怪物的概率最小，可以求最大的遇不到怪物的概率。就是在SPFA中当距离相同时维护概率最大就行了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = ;
const int M = ;
int n,m,cnt=;
int tot=,s,t;
int head[N],dis[N],vis[N],pre[N];
double va[N];
struct man {
int to,next;
double val;
} edg[N];
void add(int u,int v,double val) {
edg[tot].to=v;
edg[tot].val=val;
edg[tot].next=head[u];
head[u]=tot++;
edg[tot].to=u;
edg[tot].val=val;
edg[tot].next=head[v];
head[v]=tot++;
}
void spfa() {
met(dis,inf);met(vis,);
dis[s]=;
queue<int>q;
q.push(s);
vis[s]=;
va[s]=;
while(!q.empty()) {
int w=q.front();
q.pop();
vis[w]=;
for(int i=head[w]; i!=-; i=edg[i].next) {
int v=edg[i].to;//printf("###%d %d %d\n",v,dis[v],dis[w]);
if(dis[v]>dis[w]+) {
dis[v]=dis[w]+;
pre[v]=w;
va[v]=va[w]*edg[i].val;
if(!vis[v]) {
vis[v]=;
q.push(v);
}
} else if(dis[v]==dis[w]+) {
if(va[w]*edg[i].val-va[v]>) {
pre[v]=w;
va[v]=va[w]*edg[i].val;
if(!vis[v]) {
vis[v]=;
q.push(v);
}
}
}
}
}
}
int main() {
int u,v,val;
met(head,-);
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
while(m--) {
scanf("%d%d%d",&u,&v,&val);
double ff=val*1.0/;
add(u,v,-ff);
}
spfa();
printf("%d %.7lf\n",dis[t],-va[t]);
stack<int>p;
for(int i=t;;i=pre[i]){
p.push(i);
if(i==s)break;
}
while(!p.empty())printf("%d ",p.top()),p.pop();printf("\n");
return ;
}