图论-商旅旅行变形问题

我就是我 2022-05-25 12:29 109阅读 0赞

看如下问题：

给定一幅n个点m条边的图和S个一定要经过的点，问从0号点出发，经过这S个点再回到0号点的最短路径长度是多少。(S<=10)

这个问题初看起来，很难解决，但是它其实是商旅旅行问题的变形。

一定要经过s个点，那我们就只经过这s个点。我们先通过dijstra跑出这S点与其他点的最短路，然后就是已知这s个点的之间的j距离，然后求从0点遍历所有点然后回到的0点的问题了。商旅旅行问题。

输入描述:  
第一行一个整数T（T <= 2)表示数据组数。  
对于每组数据，第一行两个整数n，m表示点数和边数(1 <= n, m <= 100,000)。  
接下来m行，每行三个整数x, y, z(0 < x, y < n, 0 <= z <= 1000)表示xy之间有一条长度为z的双向边；  
接下来一个整数S。(S<=10)  
接下来S行每行一个整数表示一定要经过的点。  
数据保证有解。  
输出描述:

T行，每行一个整数表示答案。

代码如下:

#include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> P;
    
    const int inf=1e9+7;
    const int maxn=1e5+100;
    struct ege
    {
        int to,cost;
    };
    vector<ege> G[maxn];
    int dis[12][maxn],point[10];
    int dp[(1<<13)][12];
    
    void dijkstra(int p)//elogn
    {
        queue<P> que;
        int s=point[p];
        fill(dis[p],dis[p]+maxn,inf);
        dis[p][s]=0;
        que.push(P(0,s));
        while (que.size()) {
            P pos=que.front();
            que.pop();
            int V=pos.second;
            if (dis[p][V]<pos.first) continue;
            for (int i=0;i<G[V].size();i++) {
                ege e=G[V][i];
                if (dis[p][e.to]>dis[p][V]+e.cost) {
                    dis[p][e.to]=dis[p][V]+e.cost;
                    que.push(P(dis[p][e.to],e.to));
                }
            }
        }
    
    }
    int main()
    {
        int t;
        cin>>t;
        while (t--) {
            int n,m;
            cin>>n>>m;
            for (int i=1;i<=m;i++) {
                int x,y,z;
                cin>>x>>y>>z;
                G[x].push_back(ege{y,z});
                G[y].push_back(ege{x,z});
            }
            int s;
            cin>>s;
            point[0]=0;
            for (int i=1;i<=s;i++) {//处理去每个点的信息
                scanf("%d",&point[i]);
                dijkstra(i);
            }
            dijkstra(0);
            for (int i=0;i<=(1<<(s+1));i++) {
                for (int j=0;j<=s;j++) {
                    dp[i][j]=inf;
                }
            }
            for (int i=0;i<=s;i++) {
                dp[1<<i][i]=dis[0][point[i]];
            }
            for (int i=0;i<(1<<(s+1));i++) {
                for (int j=0;j<=s;j++) {
                    if (dp[i][j]>=inf) continue;
                    for (int k=0;k<=s;k++) {
                        dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dis[j][point[k]]);
                    }
                }
            }
            printf("%d\n",dp[(1<<((s+1)))-1][0]);
            for (int i=0;i<=n;i++) G[i].clear();
        }
        return 0;
    }