道路和航线

末蓝、 2021-11-29 13:32 311阅读 0赞

### 问题 B: 道路和航线 ###

时间限制: 1 Sec  内存限制: 128 MB  
提交: 56  解决: 20  
\[[提交][Link 1]\] \[[状态][Link 2]\] \[命题人:[admin][]\]

#### 题目描述 ####

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号城镇。

## 题意： ##

中文题意不多解释。

## 分析： ##

一看带负环的最短路，用SPFA吧。然后当场TLE。

题意说明了没有负环。双向边总是正的。

所以可以缩点，得到一个DAG。

每个联通块内做dijstra，然后各个联通块之间拓扑更新最短路就行了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

///  author:Kissheart  ///
    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    #include<vector>
    #include<stdlib.h>
    #include<math.h>
    #include<queue>
    #include<deque>
    #include<ctype.h>
    #include<map>
    #include<set>
    #include<stack>
    #include<string>
    #define INF 0x3f3f3f3f
    #define FAST_IO ios::sync_with_stdio(false)
    const double PI = acos(-1.0);
    const double eps = 1e-6;
    const int MAX=1e5+10;
    const int mod=1e9+7;
    typedef long long ll;
    using namespace std;
    #define gcd(a,b) __gcd(a,b)
    inline ll lcm(ll a,ll b){
          return a/gcd(a,b)*b;}
    inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){
         if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
    inline ll inv1(ll b){
          return qpow(b,mod-2);}
    inline ll exgcd(ll a,ll b,ll &x,ll &y){
         if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
    inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
    //freopen( "in.txt" , "r" , stdin );
    //freopen( "data.txt" , "w" , stdout );
    int n,r,p,s;
    int kuai[MAX],sum;
    int in[MAX],dis[MAX];
    int vis[MAX];
    vector<int>comp[MAX];
    vector<pair<int,int> >road[MAX],plane[MAX];
    void DFS(int x,int sum)
    {
        kuai[x]=sum;
        comp[sum].push_back(x);
        for(auto to:road[x])
        {
            if(!kuai[to.first])
                DFS(to.first,sum);
        }
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&r,&p,&s);
        while(r--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            road[u].push_back(make_pair(v,w));
            road[v].push_back(make_pair(u,w));
        }
        while(p--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            plane[u].push_back(make_pair(v,w));
        }
        for(int i=1;i<=n;i++)
            if(!kuai[i])
                DFS(i,++sum);
        for(int i=1;i<=n;i++)
            for(auto x:plane[i])
                in[kuai[x.first]]++;
        fill(dis+1,dis+1+n,INF);
        dis[s]=0;
        queue<int>Q;
        for(int i=1;i<=sum;i++)
            if(!in[i])
                Q.push(i);
    
        while(!Q.empty())
        {
            int k=Q.front();
            Q.pop();
            priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > >pq;
            for(auto x:comp[k])
                if(dis[x]<INF)
                    pq.push(make_pair(dis[x],x));
            while(!pq.empty())
            {
                pair<int,int> k=pq.top();
                pq.pop();
                if(vis[k.second]) continue;
                vis[k.second]=1;
                for(auto x:road[k.second])
                    if(x.second+dis[k.second]<dis[x.first])
                        pq.push(make_pair(dis[x.first]=x.second+dis[k.second],x.first));
    
                for(auto x:plane[k.second])
                    dis[x.first]=min(dis[x.first],dis[k.second]+x.second);
            }
            for(auto x:comp[k])
                for(auto t:plane[x])
                    if(--in[kuai[t.first]]==0)
                        Q.push(kuai[t.first]);
        }
        for(int i=1;i<=n;i++)
        {
            if(dis[i]==INF)
                printf("NO PATH\n");
            else
                printf("%d\n",dis[i]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Kissheart/p/11213853.html

[Link 1]: http://icpc.upc.edu.cn/submitpage.php?cid=1435&pid=1&langmask=262132
[Link 2]: http://icpc.upc.edu.cn/problemstatus.php?id=7922
[admin]: http://icpc.upc.edu.cn/userinfo.php?user=admin
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/97fa4a44b99042c69ada8291af4fcc96.png