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=400000 +100;
int head[N],ver[N],Next[N],edge[N],vis[N],dis[N],tot;
void add_edge(int a,int b,int c)
{
    edge[tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot++;
}
void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    deque<int> q;
    dis[s]=0;
    vis[s]=true;
    q.push_back(s);
    while(q.size())
    {
        int now=q.front();
        vis[now]=false;
        q.pop_front();
        for(int i=head[now]; ~i; i=Next[i])
        {
            int j=edge[i];
            if (dis[j]>dis[now]+ver[i])
            {
                dis[j]=dis[now]+ver[i];
                if (!vis[j])
                {
                    vis[j]=true;
                    if (q.size() && dis[j]<dis[q.front()])
                        q.push_front(j);
                    else
                        q.push_back(j);
                }
            }
        }
    }
}
int main()
{
    int t,r,p,s,x,y,z;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t>>r>>p>>s;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=r; i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
    for(int i=1; i<=p; i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
    }
    spfa(s);
    for(int i=1; i<=t; i++)
    {
        if (dis[i]==0x3f3f3f3f)
            cout<<"NO PATH"<<endl;
        else
            cout<<dis[i]<<endl;
    }
    return 0;
处。

  

原文地址:https://www.cnblogs.com/ruanmowen/p/12708306.html

时间: 04-15

ACwing 342. 道路与航线的相关文章

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),

道路和航线

题目描述 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 &l

[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

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这篇代码不错,讲得也很好. 在每个无向边联通块中找最短路可以直接迪杰.至于过度到不同的联通块,可以对无向图联通块

算法提高课——图论

图论难点:问题的转化和抽象(可看成特殊的某一类DP) 图论与DP的联系: DP问题(从集合角度分析最优化问题)可以看成从F(0,0).F(0,1).F(1,2)......F(0,m)到F(n,m)的最长路.因此DP问题可以转化为拓扑图(一般DP问题的状态间无环)上的最短(长)路. 当DP依赖关系不具有拓扑序时(即存在环时),可以将其转化为最短路,也可以用高斯消元. //TLE的原因常常是没有memsert //st数组在不同算法中的用法: 单源最短路的建图方式 AcWing 1129. 热浪

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.完全图:一个无向图,图中任