BZOJ 2200 道路与航线

好厉害呀这道题,有种豁然开朗的感觉。。。。

按拓扑顺序跑最短路。

然后注意细节,像WA的代码犯下的错是一笔带过没有丝毫考虑的。。。然而就是错了。

考试的时候一定要拍啊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define maxv 25050
#define maxe 200050
#define inf 1000000000
using namespace std;
struct status
{
    int len,v;
    bool operator < (const status &x) const
    {
        return len>x.len;
    }
    status (int v,int len):v(v),len(len){}
    status () {}
};
int n,m1,m2,s,dis[maxv],d[maxv],father[maxv],g[maxv],nume=1,tot=0,x,y,z,bel[maxv];
vector <int> v[maxv],fr[maxv],to[maxv],w[maxv];
vector <status> bl[maxv];
map <int,int> mp;
queue <int> qr;
priority_queue <status> q;
struct edge
{
    int v,w,nxt;
}e[maxe];
void addedge(int u,int v,int w)
{
    e[++nume].v=v;
    e[nume].w=w;
    e[nume].nxt=g[u];
    g[u]=nume;
}
int getfather(int x)
{
    if (father[x]!=x) father[x]=getfather(father[x]);
    return father[x];
}
void unionn(int x,int y)
{
    int f1=getfather(x),f2=getfather(y);
    if (f1==f2) return;
    father[f2]=f1;
}
void dijkstra(int x)
{
    for (int i=0;i<bl[x].size();i++) dis[bl[x][i].v]=min(dis[bl[x][i].v],bl[x][i].len);
    for (int i=0;i<v[x].size();i++) if (dis[v[x][i]]!=inf) q.push(status(v[x][i],dis[v[x][i]]));
    while (!q.empty())
    {
        status head=q.top();q.pop();
        for (int i=g[head.v];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if (dis[v]>dis[head.v]+e[i].w)
            {
                dis[v]=dis[head.v]+e[i].w;
                q.push(status(v,dis[v]));
            }
        }
    }
}
void topusort()
{
    for (int i=1;i<=tot;i++)
    {
        if (!d[i]) qr.push(i);
        bl[i].push_back(status(v[i][0],inf));
    }
    while (!qr.empty())
    {
        int head=qr.front();qr.pop();
        if (head==bel[s]) bl[bel[s]].push_back(status(s,0));
        dijkstra(head);
        for (int i=0;i<fr[head].size();i++)
        {
            if (dis[fr[head][i]]!=inf)
            {
                status now=status(to[head][i],dis[fr[head][i]]+w[head][i]);
                bl[bel[to[head][i]]].push_back(now);
            }
            if (!--d[bel[to[head][i]]]) qr.push(bel[to[head][i]]);
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m1,&m2,&s);
    for (int i=1;i<=n;i++) {father[i]=i;dis[i]=inf;}
    for (int i=1;i<=m1;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);addedge(y,x,z);
        unionn(x,y);
    }
    for (int i=1;i<=n;i++)
    {
        int f=getfather(i);
        if (!mp[f]) mp[f]=++tot;
        bel[i]=mp[f];v[mp[f]].push_back(i);
    }
    for (int i=1;i<=m2;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        fr[bel[x]].push_back(x);to[bel[x]].push_back(y);w[bel[x]].push_back(z);
        d[bel[y]]++;
    }
    topusort();
    for (int i=1;i<=n;i++)
    {
        if (dis[i]==inf) printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
    return 0;
}
时间: 11-16

BZOJ 2200 道路与航线的相关文章

道路和航线

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

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 1969: [Ahoi2005]LANE 航线规划( 树链剖分 )

首先我们要时光倒流, 倒着做, 变成加边操作维护关键边. 先随意搞出一颗树, 树上每条边都是关键边(因为是树, 去掉就不连通了)....然后加边(u, v)时, 路径(u, v)上的所有边都变成非关键边了, 因为形成了环, 环上任意2点有2条路径...下图, 加上蓝色的边, 红色x的边就变成了非关键边. 所以树链剖分维护一下...时间复杂度O(NlogN+MlogM+Qlog^2N), 可以AC. 翻了翻ZY的标解:“动态维护树+最近公共祖先查询”....复杂度是O(NlogN+M+QlogN)

BZOJ 3575 道路堵塞

Description A国有N座城市,依次标为1到N.同时,在这N座城市间有M条单向道路,每条道路的长度是一个正整数.现在,A国交通部指定了一条从城市1到城市N的路径,并且保证这条路径的长度是所有从城市1到城市N的路径中最短的.不幸的是,因为从城市1到城市N旅行的人越来越多,这条由交通部指定的路径经常发生堵塞.现在A国想知道,这条路径中的任意一条道路无法通行时,由城市1到N的最短路径长度是多少. Input 输入文件第一行是三个用空格分开的正整数N.M和L,分别表示城市数目.单向道路数目和交通

BZOJ 1020 安全的航线flight

Description 在设计航线的时候,安全是一个很重要的问题.首先,最重要的是应采取一切措施确保飞行不会发生任何事故,但同时也需要做好最坏的打算,一旦事故发生,就要确保乘客有尽量高的生还几率.当飞机迫降到海上的时候,最近的陆地就是一个关键的因素.航线中最危险的地方就是距离最近的陆地最远的地方,我们称这种点为这条航线“孤地点”.孤地点到最近陆地的距离被称为“孤地距离”.作为航空公司的高级顾问,你接受的第一个任务就是尽量找出一条航线的孤地点,并计算这条航线的孤地距离.为了简化问题,我们认为地图是

BZOJ2200: [Usaco2011 Jan]道路和航线

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

BZOJ 2435 道路修建 NOI2011 树形DP

一看到这道题觉得很水,打了递归树形DP后RE了一组,后来发现必须非递归(BFS) 递归版本84分: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int N,point[1000003],next[2000003],v[2000003],c[2000003],cnt=0,f[1000003]; bool p[1000003]; long long sum=0; vo

BZOJ 1969: [Ahoi2005]LANE 航线规划 [树链剖分 时间倒流]

题意: 一张图,删除边,求两点之间的割边数量.保证任意时刻图连通 任求一棵生成树,只有树边可能是割边 时间倒流,加入一条边,就是两点路径上的边都不可能是割边,区间覆盖... 然后本题需要把边哈希一下,手写哈希比map快很多 貌似还有一种不用树剖的做法,不管了 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; co