P10178 陌路寻诗礼 题解

· · 题解

前言

我认为官方题解的思路和代码稍有些复杂，所以来分享一下我的思路。

代码似乎和 dijkstra 板子没差几行。

题目描述

在一个 n 个点 m 条边的无向图中构造出每条边的长度 z_i（1\leq z_i\leq k），使得点 1 到任何一个点的最短路径都是唯一的，如果不能做到，则报告无解。

思路

考场上我的做法只涉及到了普通的 dijkstra 进行略微的修改。

文中提到的 spfa 算法很好地帮助我们很好的想到了 dijkstra 算法（spfa 算法可能会被卡，而且也没有负权，因为 1\leq z_i\leq k）。

一句话总结，先写 dijkstra 板子，然后边权全部初始化为 1，如果碰上路径长度相同，则将当前这条边的边权加一，最后判断如果最大边权超过 k，则无解，否则有解，输出答案即可。

个人认为自己的思路比较简单易想且写起来很方便。

代码

相比 dijkstra 模板，基本上没改几行。

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int N=3e5+5;

struct nodee{
    int to,id;  // id 记录是第几条边
};

vector<nodee> e[N];
int n,m,k;
int T;
bool vis[N];
int dis[N];
int ans[N],mx;  // ans 数组即 z 数组，mx 记录 ans 的最大值，以便判断是否大于 k

struct node{
    int id,val;
    bool operator<(const node &o)const{ // 比较结构体大小
        return val>o.val;
    }
};

bool dijkstra(int s){   // dijkstra 板子
    memset(vis,0,sizeof vis);   // 清空很重要
    memset(dis,0x3f,sizeof dis);
    mx=-INF;    // 求最大，所以先设为一个极小值
    priority_queue<node> q; // 使用优先队列优化
    q.push({s,0});
    dis[s]=0;
    while(!q.empty()){
        int u=q.top().id;
        int val=q.top().val;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to,id=e[u][i].id;
            if(dis[v]>dis[u]+1){    // 边权都是 1，由于每条边只会遍历一次，所以修改不会影响唯一一次遍历时的边权 1
                dis[v]=dis[u]+1;
                q.push({v,dis[v]});
            }else if(dis[v]==dis[u]+1){ // 如果最短路径长度相同，那么 ++ans[id] 同时记录最大值即可
                mx=max(mx,++ans[id]);
            }
        }
    }
    return mx<=k;   // 如果最大值不超过 k 那么就有解
}

int main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)e[i].clear();  // 清空
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            e[x].push_back({y,i});  // 要记录是第 i 条边
        }
        fill(ans+1,ans+m+1,1);  // 一开始边权 ans 即 z 都设为 1
        if(dijkstra(1)){    // 有解
            puts("Yes");
            for(int i=1;i<=m;i++)cout<<ans[i]<<" \n"[i==m]; // 输出答案即可
        }else puts("No");
    }
    return 0;
}

然后就能通过本题了。