问题描述

Farmer John想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1-T。这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T),花费为C_i。
对于道路,0 <= C_i <= 10,000;然而航线的花费很神奇,花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的,可以从A_i到B_i,也可以从B_i到A_i,花费都是C_i。然而航线与之不同,只可以从A_i到B_i。
如果有一条航线可以从A_i到B_i,那么保证不可能通过一些道路和航线从B_i回到A_i。他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

输入

第1行:四个空格隔开的整数: T, R, P, and S
第2到R+1行:三个空格隔开的整数(表示一条道路):A_i, B_i 和C_i
第R+2到R+P+1行:三个空格隔开的整数(表示一条航线):A_i, B_i 和 C_i

输出

第1到T行:从S到达城镇i的最小花费,如果不存在输出”NO PATH”。

思路

最早一看以为是一个裸的SPFA,于是很愉快的花十分钟码完了,结果T了两个点。果然BZOJ没有这么水的题QWQ原来数据构造好了要卡SPFA。

正解的思路是:由于航线是单向且保证了不可能通过一些道路和航线回到本身,所以说这个图由是很多个正边权无向边组成的联通块被一些可能有负权的有向边连接起来。

这样的话就可以把每个联通块视为一个点,可以按照拓扑序在每个联通块内跑Dijkstra最后求出答案。由于一些玄学的错误,这个代码我调了整整一天还没有调出来。最后草率的在SPFA上加了SFL优化A了这题。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 25005
#define MAXE 100005
#define INF 0x3f3f3f3f
using namespace std;

struct Edge {int next, to, dis;} edge[MAXE*2];

int t, r, p, s, a, b, c, cnt, head[MAXN], dis[MAXN];
bool vis[MAXN];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void spfa()
{
    deque<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[s]=true; dis[s]=0;
    q.push_back(s);
    while(!q.empty())
    {
        int x=q.front(); q.pop_front();
        vis[x]=false;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]>dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                if(vis[to]) continue;
                vis[to]=true;
                if(dis[to]<dis[q.front()]) q.push_front(to);
                else q.push_back(to);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &t, &r, &p, &s);
    for(int i=1; i<=r; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    for(int i=1; i<=p; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
    }
    spfa();
    for(int i=1; i<=t; i++)
    {
        if(dis[i]==INF) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
    }
}

2 对 “BZOJ2200 道路和航线 [SPFA]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注