样例过了,下载第一组数据也对,但是wa,
查看原帖
样例过了,下载第一组数据也对,但是wa,
97024
李润淇楼主2025/1/21 14:08

Too short on line 1. 显示这个,但是自己测试答案是对的,

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <set>
#include <string.h>
#include <queue>
using namespace std;
typedef long long ll;
const int &ma = 1e6;
int M(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}
int Ms(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}
int n, m;
int s, en;
const int MAX = 1e7;
bool vis[MAX];
int cnt = 0, h[MAX], to[MAX], nxt[MAX];
double val[MAX], dis[MAX];
void add(int a, int b, double c)
{
    to[++cnt] = b;
    val[cnt] = 1.0000 - 0.0100 * c;
    nxt[cnt] = h[a];
    h[a] = cnt;
}
void Dij()
{
    for (int i = 1; i <= n; i++)
        dis[i] = 0.000000;
    cout<<endl;
    dis[s] = 1.000000;
    dis[0] = 0.000000;
    while (1)
    {
        int u = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[u] < dis[i])
            {
                u = i;
            }
       //     cout<<dis[i]<<endl;
        }
    //    cout<<endl;
        if (u == 0)
            break;
        vis[u] = 1;
        for (int i = h[u]; i; i = nxt[i])
        {
            if (dis[to[i]] < double(dis[u] * 1.000000) * double(val[i] * 1.000000))
            {
                dis[to[i]] = double(dis[u] * 1.000000) * double(val[i] * 1.000000);
            }
        }
    }
}
int main()
{
    int t;
    int a, b, c;
    double r;
    scanf("%d%d",&n,&m);
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%lf",&a,&b,&r);
        add(a, b, r);
        add(b, a, r);
    }
    cin >> s >> en;
    Dij();
    double ans=100/dis[en];
    printf("%.8lf", ans);
}
2025/1/21 14:08
加载中...