UVa1048 Low Cost Air Travel—

很好的一道题呀

思路

状态\(d(i,j)\)表示已经经过了行程单中的\(i\)个城市，目前在城市\(j\)的最小代价，直接建边跑最短路就行了

比如机票为\(ACBD\)，行程单为\(CD\)，那么对于\((0,A)\)，连向\((1,C)\)，\((1,B)\)，\((2,D)\)

有两个需要注意的地方

1.起点为\((1,行程单的起点)\)

2.城市编号很大，要离散化

以下是代码，离散化用\(map\)完成

#include <algorithm>

#include  <iostream>

#include   <cstdlib>

#include   <cstring>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <cmath>

#include     <ctime>

#include     <queue>

#include       <map>

#include       <set>

using namespace std;

#define ull unsigned long long

#define pii pair<int, int>

#define uint unsigned int

#define mii map<int, int>

#define lbd lower_bound

#define ubd upper_bound

#define INF 0x3f3f3f3f

#define IINF 0x3f3f3f3f3f3f3f3fLL

#define DEF 0x8f8f8f8f

#define DDEF 0x8f8f8f8f8f8f8f8fLL

#define vi vector<int>

#define ll long long

#define mp make_pair

#define pb push_back

#define re register

#define il inline

#define N 10000

struct Edge {

  int next, from, to, w, id;

}e[2000000];

int ticketCnt, routeCnt, nodeCnt, cityCnt;

int price[250], cities[250];

vi tickets[250];

map<pii, int> nodeId;

mii cityId;

pii originNode[N+5];

int head[N+5], eid;

int d[N+5], pre[N+5];

bool inq[N+5];

int stk[N+5], tp;

queue<int> q;

void addEdge(int u, int v, int w, int id) {

  e[++eid] = Edge{head[u], u, v, w, id};

  head[u] = eid;

}

void spfa() {

  memset(d, 0x3f, sizeof d);

  memset(inq, 0, sizeof inq);

  memset(pre, 0, sizeof pre);

  int S = nodeId[mp(1, cities[1])];

  d[S] = 0;

  q.push(S);

  while(!q.empty()) {

    int u = q.front(); q.pop();

    inq[u] = 0;

    for(int i = head[u]; i; i = e[i].next) {

      int v = e[i].to, w = e[i].w;

      if(d[v] > d[u]+w) {

        d[v] = d[u]+w;

        pre[v] = i;

        if(!inq[v]) inq[v] = 1, q.push(v);

      }

    }

  }

}

void mark(int u) {

  if(!pre[u]) return ;

  stk[++tp] = e[pre[u]].id;

  mark(e[pre[u]].from);

}

int main() {

  int kase = 0;

  while(~scanf("%d", &ticketCnt) && ticketCnt) {

    ++kase;

    nodeCnt = cityCnt = 0;

    nodeId.clear();

    cityId.clear();

    for(int i = 1, cnt; i <= ticketCnt; ++i) {

      scanf("%d%d", &price[i], &cnt);

      tickets[i].clear();

      for(int j = 1, x; j <= cnt; ++j) {

        scanf("%d", &x);

        if(!cityId.count(x)) cityId[x] = ++cityCnt;

        tickets[i].pb(cityId[x]);

      }

    }

    scanf("%d", &routeCnt);

    for(int t = 1, len; t <= routeCnt; ++t) {

      memset(head, 0, sizeof head);

      eid = 0;

      scanf("%d", &len);

      for(int c = 1; c <= len; ++c) {

        scanf("%d", &cities[c]);

        if(!cityId.count(cities[c])) cityId[cities[c]] = ++cityCnt;

        cities[c] = cityId[cities[c]];

      }

      for(int ticket = 1; ticket <= ticketCnt; ++ticket) {

        for(int i = cities[1] == tickets[ticket][0]; i <= len; ++i) {

          int cnt = i;

          pii cur = mp(i, tickets[ticket][0]);

          if(!nodeId.count(cur)) nodeId[cur] = ++nodeCnt, originNode[nodeCnt] = cur;

          for(int j = 1; j < tickets[ticket].size(); ++j) {

            if(cnt+1 <= len && cities[cnt+1] == tickets[ticket][j]) cnt++;

            pii newState = mp(cnt, tickets[ticket][j]);

            if(!nodeId.count(newState)) nodeId[newState] = ++nodeCnt, originNode[nodeCnt] = newState;

            addEdge(nodeId[cur], nodeId[newState], price[ticket], ticket);

          }

        }

      }

      spfa();

      printf("Case %d, Trip %d: Cost = %d\n", kase, t, d[nodeId[mp(len, cities[len])]]);

      printf("  Tickets used: ");

      tp = 0;

      mark(nodeId[mp(len, cities[len])]);

      for(int i = tp; i > 1; --i) printf("%d ", stk[i]);

      printf("%d\n", stk[1]);

    }

  }

  return 0;

}

巴特西

UVa1048 Low Cost Air Travel——最短路

思路

最新文章

热门文章