0 pts! ! ! 为什么啊??
查看原帖
0 pts! ! ! 为什么啊??
462003
tommyfj楼主2022/10/3 23:25
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int n,m,s1,s2,ans,cnt;
int u, v;
double w;
double head[2010];
double dis[2010];
bool vis[200010];
struct edge
{
    int to, next;
    double dis;
}a[200010];
struct node
{
    double dis;
    int pos;
    friend bool operator < (node a, node b) {
        return a.dis > b.dis;
    }
};
void add(int u, int v, double w)
{
    a[++ cnt].dis = w;
    a[cnt].to = v;
    a[cnt].next = head[u];
    head[u] = cnt;
}
priority_queue<node> q;
void dijkstra(int s)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1;i <= n;i ++) dis[i] = 0.0;
    dis[s] = 1.0;
    q.push({1.0, s});
    while (!q.empty())
    {
        node temp = q.top();
        q.pop();
        int x = temp.pos;
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x];i;i = a[i].next)
        {   
            int y = a[i].to;
            if (dis[y] < dis[x] * a[i].dis)
            {
                dis[y] = dis[x] * a[i].dis;
                if (!vis[y]) q.push({dis[y], y});
            }
        }
    }
}
signed main()
{
    scanf("%lld %lld", &n, &m);
    for (int i = 1;i <= m;i ++)
    {
        scanf("%lld %lld %lf", &u, &v, &w);
        add(u, v, 1.0 - w / 100.0);
        add(v, u, 1.0 - w / 100.0);
    }
    scanf("%lld %lld", &s1, &s2);
    dijkstra(s1);
    printf("%.8lf\n", 100.0 / dis[s2]);
    return 0;
}

明早来看~

2022/10/3 23:25
加载中...