题解 CF1433G 【Reducing Delivery Cost】

· · 题解

Codeforces 1433G 题解

Solution

一开始的想法是把所有最短路在途中标记出来，然后取一个 经过次数\times边权 最大的边边权置为 0，然后就成为了标准错解，WA ON TEST 2。这是因为删之前的最短路径和删之后的最短路径不一定重合，这点从样例二就可以看出来。

令 \text{dis}(x,y) 表示 x 到 y 的最短距离，那么我们要考虑的就是将一条边 (u,v) 边权置零后 \text{dis}(a_i,b_i) 会如何变化。如果想要让 \text{dis}(a_i,b_i) 变小，则最短路径一定会经过 (u,v) 这条边。显然，此时 \text{dis}(a_i,b_i)=\min\{\text{dis}(a_i,b_i),\text{dis}(a_i,u)+\text{dis}(b_i,v),\text{dis}(a_i,v)+\text{dis}(b_i,u)\}。\text{dis} 可以跑 n 遍 Dijkstra 预处理，然后枚举哪条边被删掉即可。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
inline void read(int &x)
{
    x=0; int f=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar(); 
    }
    x*=f;
}
const int N=1000,M=2000,INF=0x3f3f3f3f;
int head[N+10],ver[M+10],nxt[M+10],edge[M+10],tot=1;
void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
int dis[N+10][N+10];
bool vis[N+10];
int n,m,k;
void dij(int S)
{
    for(int i=1;i<=n;i++) dis[S][i]=INF;
    dis[S][S]=0;
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int> > que;
    que.push(make_pair(0,S));
    while(!que.empty())
    {
        int x=que.top().second; que.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=edge[i];
            if(dis[S][x]+z<dis[S][y])
            {
                dis[S][y]=dis[S][x]+z;
                que.push(make_pair(-dis[S][y],y));
            }
        }
    }
}
struct node
{
    int a,b;
//  bool operator < (const node &x) const {return a==x.a?b<x.b:a<x.a;}
//  bool operator == (const node &x) const {return a==x.a && b==x.b;}
}s[N+10];
int U[N+10],V[N+10];
int main()
{
    read(n);read(m);read(k);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        read(u);read(v);read(w);
        U[i]=u;V[i]=v;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++) dij(i);
    for(int i=1;i<=k;i++) 
    {
        read(s[i].a);
        read(s[i].b);
    }
//  sort(s+1,s+k+1);
//  k=unique(s+1,s+k+1)-s-1;
    int ans=INF;
    for(int i=1;i<=m;i++)
    {
        int sum=0;
        for(int j=1;j<=k;j++)
            sum+=min(dis[s[j].a][s[j].b],min(dis[s[j].a][U[i]]+dis[V[i]][s[j].b],dis[s[j].a][V[i]]+dis[U[i]][s[j].b]));
        ans=min(ans,sum);
    }
    printf("%d",ans);
    return 0;
}