P9813 [CCC 2015 S4] Convex Hull题解

xpsroc · 2023-10-27 20:35:19 · 题解

Solution

一眼看此题有两个边权好像很复杂。

再看数据范围，直接分层图也炸不了。

按照第二个边权的值分层图，这样按照数据最多分二百层的图。

只需要每次建边时把每层图的起点与加上第二个边权的另一层图的终点建边就好了（当然不要忘记建本题为无向图）。

最后跑一遍 Dijkstra 就可以了。

接下来放代码。

Code

#include<iostream>
#include<cstdio>
#include<functional>
#include<queue>
using namespace std;
#define int long long
const int N=2050;
int k,n,m,s,t;
typedef pair<int,int >pr;
priority_queue<pr, vector<pr >, greater<pr> >q;
int h[N*205],d[N*205],vis[N*205];//写分层图别忘了数组范围 
struct ed{
    int ne,to,sum;
}a[40100000];
int cnt=0;
void add(int u,int v,int w){
    a[++cnt].ne=h[u];a[cnt].to=v;a[cnt].sum=w;
    h[u]=cnt;
}
const int Inf=0x7f7f7f7f;
signed main(){
    cin>>k>>n>>m;
    for(int i=1; i<=m; i++){
        int ax,bx,cx,dx;cin>>ax>>bx>>cx>>dx;
        for(int j=0; j<=k; j++){
            add(ax+j*n,bx+j*n+dx*n,cx);//分层图核心思想 
            add(bx+j*n,ax+j*n+dx*n,cx);//建两条边 
        }
    }
    cin>>s>>t;
    //Dijkstra 
    for(int i=1; i<=n*204; i++)d[i]=Inf;
    q.push(make_pair(0,s));d[s]=0;
    while(!q.empty()){
        pr it=q.top();q.pop();
        int kkx=it.first,u=it.second;
        if(vis[u]==1)continue;
        vis[u]=1;
        for(int i=h[u]; i!=0; i=a[i].ne){
            int v=a[i].to;
            if(d[v]>d[u]+a[i].sum){
                d[v]=d[u]+a[i].sum;
                q.push(make_pair(d[v],v));
            }
        }
    }
    int anss=Inf;
    for(int i=0; i<k; i++){
        if(d[t+i*n]!=Inf)anss=min(anss,d[t+i*n]);
    }//判断只需要前k层中有一层的终点能到达就行了。 
    if(anss==Inf)cout<<-1<<endl;
    else cout<<anss<<endl;
}