跳到主要内容

单源最短路的综合应用

AcWing 1135. 新年好​

题目​

重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站。 每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。 在一条路径上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e。 过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。 怎样走，才需要最少的时间？

思路​

预处理，求六遍dijkstra，处理出1,a,b,c,d,e到图中各点的单源最短路。 然后枚举所有从1出发的方案，比如1->a->c->d->b->e就是其中之一，将这些方案的路径和求个最小值即可

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=50010,M=200010,INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int source[6],dist[6][N];
bool st[N];

void add(int a,int b,int c)
{
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(int start,int dist[])
{
    memset(dist, 0x3f, N * 4);
    dist[start]=0;
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,start});
    while (heap.size())
    {
        PII t=heap.top();heap.pop();
        int u=t.second,distance=t.first;
        if(st[u]) continue;
        st[u]=true;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int dfs(int u,int start,int distance)
{
    if(u>5) return distance;
    int res=INF;
    for(int i=1;i<=5;i++)
    {
        if(!st[i])
        {
            int Next=source[i];
            st[i]=true;
            res=min(res,dfs(u+1,i,distance+dist[start][Next]));
            st[i]=false;
        }
    }
    return res;
}


int main()
{
    cin>>n>>m;
    source[0]=1;
    for(int i=1;i<=5;i++) cin>>source[i];

    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=0;i<6;i++) dijkstra(source[i],dist[i]);
    memset(st,0,sizeof st);
    cout<<dfs(1,0,0);
    return 0;
}

AcWing 340. 通信线路​

题目​

https://www.acwing.com/problem/content/342/ 在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 Li。 农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。 农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱可以完成升级。

思路​

单源最短路+二分 原问题转换为：求这样一个x，使得【1->n的路径上的边权>x的数量】<=k， 为了证明我们所求的答案的确可以通过二分来找到，我们需要说明所求的答案具有某种性质，且在它的右边满足，左边不满足： 1.对于答案x，需要满足的性质就是从1走到n需要经过大于x的边数小于等于k，作为分界点，此时大于x的边数应该等于k。 2.对于答案右边的区间，x变大了，大于x的边数就会减小，即大于x的边数小于k，同样满足性质； 3.对于答案左边的区间，x变小了，大于x的边数就会增加，即大于x的边数大于k，不满足性质。 在01图中找最短路径，可以使用双端队列来做，通过不断二分就可以找到最小的第k+1大的数。

代码​

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=1010,M=20010;
int n,m,k;
int h[N],e[M],ne[M],w[M],idx;
deque<int> q;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool check(int bound)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1]=0;

    q.push_back(1);
    while (q.size())
    {
        int t=q.front();q.pop_front();
        if(st[t]) continue;
        st[t]=true;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i],x=w[i]>bound;
            if (dist[j] > dist[t] + x)
            {
                dist[j]=dist[t]+x;
                if(!x) q.push_front(j);//0加到队头
                else q.push_back(j);
            }
        }
    }
    return dist[n]<=k;
}

int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    int l=0,r=1e6+1;

    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    if(r==1e6+1) r=-1;
    cout<<r<<endl;
    return 0;
}

0%