计蒜客 - 电能传输(最短路)

题目链接:https://nanti.jisuanke.com/t/10772

• 5000ms
• 262144K

题目描述

在嘟嘟生活的王国有 n 座城市，某些城市之间有传输电能的线路。在某条线路传输电能是会有损耗的，某一个城市在某一时间只可以向另外一个城市传输电能。已知在城市 s 存在 m 千瓦时电能，求将这些电能都传输到城市 t ，至少需要损耗多少电能。

输入格式

输入包含多组测试数据，对于每组测试数据：
第一行包含一个整数 n ( 0 < n ≤ 50000 ) 。
接下来输入包含 n 部分，对于第 i ( 1 ≤ i ≤ n )部分：第一行包含一个整数 num ( num ≤ 50 ) ，表示城市 i 可以向 num 个城市传输电能；接下来 num 行每行包含两个整数 x y ( 1 ≤ x ≤ n ; x != i ; 0 ≤ y ≤ 100 ) ，表示城市 i 可以向城市 x 传输电能，在传输时将会损失 y% 的电能。

最后一行包含三个整数 s t m ( 1 ≤ s,t ≤ n ; 1 ≤ m ≤ 1000000 ) 。

输出格式

对于每组测试数据，如果城市 s 不能向城市 t 传输电能，则输出 "IMPOSSIBLE!" ；否则输出一个小数，表示损失电能的最小量，结果保留两位小数。

样例输入

5
2
2 20
3 40
2
3 90
4 50
2
2 40
4 90
1
5 80
0
1 5 1000

样例输出

920.00

解题思路

这是一道最短路问题，用dis[i]存s到t的最小损失，再用一个数组把传送到每个地点的电能存下来，以便计算下一个的损失，然后跑一遍最短路就行了。
Dijkstra:

#include <stdio.h>
#include <string.h>
#define N 50000
const double inf = 99999999;
int vis[N + 10], f[N + 10], n, cnt;
double dis[N + 10], arr[N + 10], minn;
struct edge {
    int u, v;
    double w;
}e[N * 50 + 10];
void Add(int u, int v, int w)
{
    e[++cnt] = (edge){f[u], v, w / 100.0};
    f[u] = cnt;
}
void Dijkstra(int s, int m)
{
    int k;
    dis[s] = 0;
    arr[s] = m;
    for (int i = 1; i <= n; i++)
    {
        minn = inf;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < minn)
                minn = dis[k = j];
        vis[k] = 1;
        for (int j = f[k]; j; j = e[j].u)
        {
            int v = e[j].v;
            if (e[j].w < 1 && !vis[v]&&dis[v] > dis[k] + arr[k] * e[j].w)
            {
                dis[v] = dis[k] + arr[k] * e[j].w;
                arr[v] = arr[k] * (1 - e[j].w);
            }
        }
    }
}
int main()
{
    int m, num, x, y, s, t;
    while (~scanf("%d", &n))
    {
        cnt = 0;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
        {
            vis[i] = 0;
            arr[i] = dis[i] = inf;
            for (int j = f[i]; j; j = e[j].u)
                e[j].w = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &num);
            while (num--)
            {
                scanf("%d%d", &x, &y);
                Add(i, x, y);
            }
        }
        scanf("%d%d%d", &s, &t, &m);
        Dijkstra(s, m);
        if (dis[t] < inf)
            printf("%.2f\n", dis[t]);
        else printf("IMPOSSIBLE!\n");
    }
    return 0;
}

Dijkstra队列优化:

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define N 50000
using namespace std;
typedef pair <double, int> PII;
const double inf = 99999999;
int vis[N + 10], f[N + 10], n, cnt;
double dis[N + 10], arr[N + 10], minn;
struct edge {
    int u, v;
    double w;
}e[N * 50 + 10];
void Add(int u, int v, int w)
{
    e[++cnt] = (edge){f[u], v, w / 100.0};
    f[u] = cnt;
}
void Dijkstra(int s, int m)
{
    priority_queue <PII, vector<PII>, greater<PII> > Q;
    dis[s] = 0;
    arr[s] = m;
    Q.push(PII(0, s));
    while (!Q.empty())
    {
        PII u = Q.top();
        Q.pop();
        if (vis[u.second])
            continue;
        vis[u.second] = 1;
        for (int j = f[u.second]; j; j = e[j].u)
        {
            int v = e[j].v;
            if (dis[v] > u.first + arr[u.second] * e[j].w)
            {
                dis[v] = u.first + arr[u.second] * e[j].w;
                arr[v] = arr[u.second] * (1 - e[j].w);
                Q.push(PII(dis[v], v));
            }
        }
    }
}
int main()
{
    int m, num, x, y, s, t;
    while (~scanf("%d", &n))
    {
        cnt = 0;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
        {
            vis[i] = 0;
            arr[i] = dis[i] = inf;
            for (int j = f[i]; j; j = e[j].u)
                e[j].w = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &num);
            while (num--)
            {
                scanf("%d%d", &x, &y);
                Add(i, x, y);
            }
        }
        scanf("%d%d%d", &s, &t, &m);
        Dijkstra(s, m);
        if (dis[t] < inf)
            printf("%.2f\n", dis[t]);
        else printf("IMPOSSIBLE!\n");
    }
    return 0;
}

Spfa: 

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define N 50000
using namespace std;
const double inf = 99999999;
int vis[N + 10], f[N + 10], n, cnt;
double dis[N + 10], arr[N + 10], minn;
struct edge {
    int u, v;
    double w;
}e[N * 50 + 10];
void Add(int u, int v, int w)
{
    e[++cnt] = (edge){f[u], v, w / 100.0};
    f[u] = cnt;
}
void Spfa(int s, int m)
{
    queue <int> Q;
    Q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    arr[s] = m;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (int j = f[u]; j; j = e[j].u)
        {
            int v = e[j].v;
            if (dis[v] > dis[u] + arr[u] * e[j].w)
            {
                dis[v] = dis[u] + arr[u] * e[j].w;
                arr[v] = arr[u] * (1 - e[j].w);
                if (!vis[v])
                {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int main()
{
    int m, num, x, y, s, t;
    while (~scanf("%d", &n))
    {
        cnt = 0;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
        {
            vis[i] = 0;
            arr[i] = dis[i] = inf;
            for (int j = f[i]; j; j = e[j].u)
                e[j].w = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &num);
            while (num--)
            {
                scanf("%d%d", &x, &y);
                Add(i, x, y);
            }
        }
        scanf("%d%d%d", &s, &t, &m);
        Spfa(s, m);
        if (dis[t] < inf)
            printf("%.2f\n", dis[t]);
        else printf("IMPOSSIBLE!\n");
    }
    return 0;
}