道路和航线

题目描述

Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接。每条道路i或者航线i连接城镇Ai (1 <= Ai <= T)到Bi (1 <= Bi <= T),花费为Ci。对于道路,0 <= Ci <= 10,000;然而航线的花费很神奇,花费Ci可能是负数(-10,000 <= Ci <= 10,000)。道路是双向的,可以从Ai到Bi,也可以从Bi到Ai,花费都是Ci。然而航线与之不同,只可以从Ai到Bi。事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台 了一些政策保证:如果有一条航线可以从Ai到Bi,那么保证不可能通过一些道路和航线从Bi回到Ai。由于FJ的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

输入

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

输出

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

样例输入

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

样例输出

NO PATH
NO PATH
5
0
-95
-100

提示

一共六个城镇。在1-2,3-4,5-6之间有道路,花费分别是5,5,10。同时有三条航线:3->5,
4->6和1->3,花费分别是-100,-100,-10。FJ的中心城镇在城镇4。
FJ的奶牛从4号城镇开始,可以通过道路到达3号城镇。然后他们会通过航线达到5和6号城镇。
但是不可能到达1和2号城镇。

正解应该是Tarjan缩点之后,对每一个联通块内部跑dijkstra,联通块之间跑拓扑序,但这样太难写了。

就写了个优化版的Spfa

具体操作是用一个双端队列。

#include <bits/stdc++.h>
#define  maxn 55055
using namespace std;
const int inf =1e9;
struct Edge
{
    int v,w,next;
};
struct M
{
    Edge edge[maxn*4];
    int head[maxn];
    int cnt;
    void init()
    {
        memset(head,-1, sizeof(head));
        cnt=0;
    }
    void addedge(int u,int v,int w)
    {
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        edge[cnt].w=w;
        head[u]=cnt++;
    }
}Mp;
int dist[maxn];
bool vis[maxn];
void Spfa(int s)
{
    deque<int> q;
    q.push_back(s);
    for(int i=1;i<maxn;i++) dist[i]=inf;
    dist[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        vis[u]=false;
        for(int i=Mp.head[u];i!=-1;i=Mp.edge[i].next)
        {
            int v=Mp.edge[i].v;
            int w=Mp.edge[i].w;
            if(dist[v]>dist[u]+w)
            {
                dist[v]=dist[u]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    if(!q.empty()&&dist[q.front()]>dist[v]) q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n,r,p,s;
    Mp.init();
    scanf("%d%d%d%d",&n,&r,&p,&s);
    for(int i=1;i<=r;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Mp.addedge(u,v,w);
        Mp.addedge(v,u,w);
    }
    for(int i=1;i<=p;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Mp.addedge(u,v,w);
    }
    Spfa(s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]!=inf) printf("%d\n",dist[i]);
        else printf("NO PATH\n");
    }
}

  

每次入队时比较队首与入队元素的距离,如果队首较大,放到队首,否则放到队尾

原文地址:https://www.cnblogs.com/zyf3855923/p/9651768.html

时间: 09-14

道路和航线的相关文章

[Usaco2011 Jan]道路和航线

Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过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

AcWing 道路与航线

AcWing 道路与航线 Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过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),

BZOJ 2200 道路与航线

好厉害呀这道题,有种豁然开朗的感觉.... 按拓扑顺序跑最短路. 然后注意细节,像WA的代码犯下的错是一笔带过没有丝毫考虑的...然而就是错了. 考试的时候一定要拍啊. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #define

BZOJ2200: [Usaco2011 Jan]道路和航线

n<=25000个点m1<=50000条正权无向边m2<=50000条正负权有向边,保证有向边连接的无向边联通块形成一个拓扑图,求从s到每个点最短路. 第一次发现不会最短路.没看题乱写迪杰无脑WA,很好.迪杰从来不能处理负权最短路,然后就开始啃题解..http://www.cnblogs.com/staginner/archive/2012/10/01/2709487.html这篇代码不错,讲得也很好. 在每个无向边联通块中找最短路可以直接迪杰.至于过度到不同的联通块,可以对无向图联通块

ACwing 342. 道路与航线

首先看到这道题目,我们发现这道题目的复杂度,首先确定了是O(nlogn)O(nlogn)级别的,所以说,我们的算法初步确定在dijskra和SPFA上面. 但是我们发现这道题目一个关键点,就是题目中出现了负权边. 一旦出现了负权边,那么我们只能使用SPFA. 关于SPFA优化https://www.cnblogs.com/TFLS-gzr/p/10389141.html #include <bits/stdc++.h> using namespace std; const int N=4000

2017/07/25 杂题(完全不可做题(划去))选讲

先膜一发主讲人@Antileaf 真是核平的一天那--大脑已经被蹂躏的死去活来了-- cogs2421 简单的Treap 链接:http://cogs.pro/cogs/problem/problem.php?pid=2421 题意:什么都给你了,建出Treap,输出先序遍历顺序. 实际上只是用了Treap的原则建树--先按照数值大小排序,然后按照建立笛卡尔树方法,维护单调栈,最大的全扔到右儿子去即可. 1 #include<iostream> 2 #include<cstdio>

bzoj2702[SDOI2012]走迷宫

题意:给你一个有向图,点数10000,边数1000000,SCC大小不超过100(按数据范围的写法只有第三部分数据满足这个条件,不过第二部分数据并没有出现大小大于100个点的SCC,我是用数组大小为100的代码以身试法的2333)从s出发随机走,问走到t的期望步数. 首先考虑inf的情况.如果从s出发可以走到一个无法走到t的点,比如这个数据:红色点为起点,绿色点为终点,那么有1/2的概率永远也走不到(在蓝色点停下). 注意出现环的情况不一定是INF,因为在环上走无穷步的概率可能是无穷小.于是先缩

DP&amp;图论 DAY 4 下午图论

DP&图论  DAY 4  下午 后天考试不考二分图,双联通 考拓扑排序 图论 图的基本模型 边: 有向边构成有向图 无向边构成无向图 权值: 1.无权 2.点权 3.边权 4.负权(dij不可以跑) 环: 1. 2.重边 3.有向无环图DAG 路径: 1.简单路径:不经过重复的点  1-->2-->3 不简单路径:经过重复点  1-->2-->3-->1-->4 2.连通,具有传递性 图: 1.树:n个点,n-1条边的无环连通图 2.完全图:一个无向图,图中任

乱七八糟的图论1

图的基本概念 图是点和边组成的集合体,G=<V,E>; V是点集 E是边集 有向边,有向图 无向边,无向图 无权.点权.边权.负权 环.自环.重边.有向无环图(DAG) 路径.简单路径:没有经过重复的点.连通 树:n个点n-1条边的连通图.完全图:任何两点间都有一条边(无向图).竞赛图:将完全图上的每条边定一个方向.基环树:有一个环,其他全是树.仙人掌:可以存在环,但是每一条边,至多只存在于一个环中 图的输入方式 最常见的输入方式是用 1 - N 表示顶点,并逐行给出 M 条边所连接的两点和边