Week3训练赛（图论）

unknown_risk · 2025-10-09 00:05:08 · 个人记录

A:Restoring Road Network

Sol： 任意两点最短路径已经给出。对于不同的三点，若存在a[i][k]+a[k][j]<a[i][j]，则不存在修复道路的方案满足题意，因为i点通过k点转移到j点才是最短路径。若a[i][k]+a[k][j]=a[i][j]，说明i点通过k点转移到j点的路径是必要的，而i直接连向j的路径可以省去。当k取任意不同于i和j的点都有a[i][k]+a[k][j]>a[i][j]，则这条路径是必要的。

C:Score Attack

Sol： 本题求的是1到n的最长路，如果路径能无限长（可到达）则输出inf。其实只需要判断从1到n的路径上是否存在正环，n不一定要在环上

D:Train

Sol： dijkstra模板，只是路径长的计算方式略有不同。因为到达了不一定立马换乘，还包含等待时间。

E:Small Multiple

Sol： 同余最短路好题。如何将这个问题抽象成一个图论问题呢？我们给当前的任意数在末尾添加一个数字x，那么它mod K的余数会发生改变（可能不变），且它的数位和增加了x。假设最后得到的数最高位是u，则我们可以将这个问题看成节点u%k到节点0的最短路，每一次转移，我们可以从0-9枚举下一位。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int k,dis[N],minn=0x3f;
bool vis[N];
struct node
{
    int tot,x;
    bool operator<(const node &s)const
    {
        return s.tot<tot; 
    }
};
priority_queue<node>q;
void solve(int x)
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,false,sizeof vis);
    while(q.size())q.pop();
    dis[x%k]=x;
    q.push({dis[x%k],x%k});
    while(q.size())
    {
        node s=q.top();
        q.pop();
        if(s.x%k==0)break;
        if(vis[s.x%k])continue;
        vis[s.x%k]=true;
        for(int i=0;i<=9;i++)
        {
            if(dis[(s.x*10+i)%k]>dis[s.x%k]+i)
            {
                dis[(s.x*10+i)%k]=dis[s.x%k]+i;
                if(!vis[(s.x*10+i)%k])q.push({dis[(s.x*10+i)%k],(s.x*10+i)%k});
            }
        }
    }
    minn=min(minn,dis[0]);
}
signed main()
{
    cin>>k;
    for(int i=1;i<=9;i++)solve(i);
    cout<<minn; 
    return 0;
}