[ABC079D] Wall 题解

Redamancy_Lydic · 2024-07-31 22:19:10 · 题解

这道题显然可以用 dijkstra 来写。

根据题目上的条件，我们要求出来每个数字到 1 的代价，那么反过来想，我们只要根据表格反向建边，然后做一遍以 1 为起点的单源最短路，那么在此条件下每个点的答案就是它跑到 1 的最小代价。

邻接表存储。

Code

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define map gp_hash_table
using namespace std;
using namespace __gnu_pbds;
const int mod=998244353;
inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
    return w*s;
}
const int maxn=1e6+10;
struct no
{
    int y,v;
};
vector<no>G[maxn]; 
int n,m,ans;
struct dij
{
    int y,d;
    inline friend bool operator < (dij x,dij y)
    {
        return x.d>y.d;
    }
};
int dis[maxn];
bool vis[maxn];
void distla(int s)
{
    priority_queue<dij> q;
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push({1,0});
    while(!q.empty())
    {
        int u=q.top().y;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto i : G[u])
        {
            int y=i.y,v=i.v;
            if(dis[y]>dis[u]+v)
            {
                dis[y]=dis[u]+v;
                if(!vis[y])q.push({y,dis[y]});
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=0;i<=9;i++)
    {
        for(int j=0;j<=9;j++)
        {
            int x=read();
            if(i==j)continue;
//          G[i].push_back({j,x});
            G[j].push_back({i,x});
        }
    }
    distla(1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x=read();
            if(x==-1)continue;
            ans+=dis[x];
        }
    }
    cout<<ans;
    return 0;
}