分析

很套路的一道题，但是初始值初始时有点搞心态。主要是考虑到 ，很自然的想到用状压去维护。定义 为当前节点在 ，已经过了的节点状态为 。那么我们的转移也比较简单 。那么我们只需要预处理 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL N = 2e5 + 1000,M = 3e5 + 10,inf = 1e18;
LL read() {
    LL x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
#define pii pair<LL,LL>
bool vis[N];
vector<pii> G[N];
struct Edge{LL to,nxt,w;}e[N];
struct Node{
    LL pos,dis;
    bool operator <(const Node x) const {
        return dis > x.dis;
    }
};
priority_queue<Node> Q;
LL n,m,K,f[20][M],dis[20][20],A[N],B[N],dist[N];
void solve(LL S) {
    while(Q.size())Q.pop();Q.push((Node){S,dist[S]=0});
    while(Q.size()){LL x=Q.top().pos;Q.pop();if(vis[x])continue;
        vis[x]=1;for(auto E:G[x]) {
            if(dist[E.first]>dist[x]+E.second) {
                dist[E.first]=dist[x]+E.second;
                Q.push((Node){E.first,dist[E.first]});
            }
        }
    }
}
int main() {
    n=read();m=read();K = read();
    for(LL i = 1,a,b,c;i <= m;i++) {
        a=read();b=read();c=read();
        G[a].push_back(pii(b,c));
        G[b].push_back(pii(a,c));
    }
    for(LL i = 1;i <= K;i++) A[i]=read(),B[i]=read();
    for(LL i = 1;i <= K;i++) {
        // memset(dist,0x3f,sizeof(dist));memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++)dist[j]=inf,vis[j]=0;
        solve(B[i]);
        for(LL j = 1;j <= K;j++) dis[i][j] = dist[A[j]];
    }
    for(int i=1;i<(1<<K);i++) {
        for(int j=1;j<=K;j++)f[j][i]=inf;
    }
    for(LL i = 1;i <= K;i++) f[i][1<<i-1] = dis[i][i];
    for(int s=1;s<(1<<K);s++){
        for(int i=1;i<=K;i++)if(s&(1<<(i-1))){
            for(int j=1;j<=K;j++){
                if(s&(1<<(j-1))) continue;
                f[j][s|(1<<(j-1))]=min(f[j][s|(1<<(j-1))],f[i][s]+dis[i][j]+dis[j][j]);
            }
        }
    }
    LL ans = inf;
    for(LL i=1;i<=K;i++) ans=min(f[i][(1<<K)-1],ans);
    if(ans>=inf)cout<<"-1"<<endl;
    else cout<<ans<<endl;return 0;
}