Link

传送门

Problem

You have just moved into a new apartment and have a long list of items you need to buy. Unfortunately, to buy this many items requires going to many different stores. You would like to minimize the amount of driving necessary to buy all the items you need.

Your city is organized as a set of intersections connected by roads. Your house and every store is located at some intersection. Your task is to find the shortest route that begins at your house, visits all the stores that you need to shop at, and returns to your house.

Mean

有N个城市M条道路,你居住在编号为0的城市,你需要从0出发游览S个城市最后回到城市0,问你最少需要走多少路。

Analysis

经典的旅行商问题,需要经过的点最多10个,所以先求出每个点作为起点到其他各点的单源最短路,然后枚举经过的先后次序即可(可以next_permutation也可以dfs)。

Code(dijkstra)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
    int to, cost;
    Edge(int to, int cost):to(to), cost(cost) {}
};
const int maxn = 102400, inf = 0x3f3f3f3f;
int N, M, D[20][maxn], V[20], pos[maxn];
vector<Edge> G[maxn];

void dijkstra(int s, int d[]) {
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P>> qu;
    qu.push(P(0, s));
    while (!qu.empty()) {
        P p = qu.top(); qu.pop();
        int u = p.second;
        if (d[u] < p.first) continue;
        for (Edge &e : G[u]) {
            if (d[e.to] > p.first + e.cost) {
                d[e.to] = p.first + e.cost;
                qu.push(P(d[e.to], e.to));
            }
        }
    }
}


int main()
{
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        for(int i = 0; i < maxn; ++i)
            G[i].clear();
        memset(D, inf, sizeof(D));
        for(int i = 0; i < M; ++i) {
            int x, y, w; scanf("%d%d%d", &x, &y, &w);
            G[x].push_back(Edge(y, w));
            G[y].push_back(Edge(x, w));
        }
        int S; scanf("%d", &S);
        for(int i = 1; i <= S; ++i)
            scanf("%d", V + i);
        sort(V + 1, V + S + 1);
        dijkstra(0, D[0]);
        for(int i = 1; i <= S; ++i) {
            dijkstra(V[i], D[i]);
            pos[V[i]] = i;
        }
        int best = inf;
        do {
            int cur = D[0][V[1]] + D[0][V[S]];
            for(int i = 1; i < S; ++i)
                cur += D[pos[V[i]]][V[i+1]];
            best = min(best, cur);
        } while(next_permutation(V + 1, V + S + 1));
        printf("%d\n", best);
    }
    return 0;
}

Code(SPFA)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
    int to, cost;
    Edge(int to, int cost):to(to), cost(cost) {}
};
const int maxn = 102400, inf = 0x3f3f3f3f;
int N, M, D[20][maxn], V[20], pos[maxn];
int inq[maxn], cnt[maxn];
vector<Edge> G[maxn];

bool spfa(int st, int d[]) {
    queue<int> qu;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    d[st] = 0; inq[st] = true; qu.push(st);
    while(!qu.empty()) {
        int u = qu.front(); qu.pop();
        inq[u] = false;
        for(int i = 0; i < G[u].size(); ++i) {
            Edge &e = G[u][i];
            if(d[u] < inf && d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                if(!inq[e.to]) {
                    qu.push(e.to);
                    inq[e.to] = true;
                    if(++cnt[e.to] > N)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        for(int i = 0; i < maxn; ++i)
            G[i].clear();
        memset(D, inf, sizeof(D));
        for(int i = 0; i < M; ++i) {
            int x, y, w; scanf("%d%d%d", &x, &y, &w);
            G[x].push_back(Edge(y, w));
            G[y].push_back(Edge(x, w));
        }
        int S; scanf("%d", &S);
        for(int i = 1; i <= S; ++i)
            scanf("%d", V + i);
        sort(V + 1, V + S + 1);
        spfa(0, D[0]);
        for(int i = 1; i <= S; ++i) {
            spfa(V[i], D[i]);
            pos[V[i]] = i;
        }
        int best = inf;
        do {
            int cur = D[0][V[1]] + D[0][V[S]];
            for(int i = 1; i < S; ++i)
                cur += D[pos[V[i]]][V[i+1]];
            best = min(best, cur);
        } while(next_permutation(V + 1, V + S + 1));
        printf("%d\n", best);
    }
    return 0;
}

欢迎留言