(UVA) 11284 - Shopping Trip

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2259&mosmsg=Submission+received+with+ID+17741643

基本的想法：位元dp

複雜度：O(2^p * p^2)

先用spfa求最短路徑(注意會有1-->0 cost 1.9, 0-->1 cost 3 的情況)

基本的想法是說：紀錄每個狀態 & 每個狀態最後是誰，最後在走訪一下即可。

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 53;
const int MAX_M = 1003;
const int MAX_P = 14;
const int INF = 1e9+7;

int w[MAX_N][MAX_N];
vector<int> edg[MAX_N];
int d[MAX_N][MAX_N];
int dp[1<<MAX_P][MAX_P];
int cost[MAX_N];
bool in_que[MAX_N];
int store[MAX_P];

void init() {
 for (int x=0;MAX_N>x;x++) {
  for (int y=0;MAX_N>y;y++) {
   w[x][y] = d[x][y] = INF;
  }
  edg[x].clear();
  cost[x]=0;
 }
 for (int x=0;x < (1<<MAX_P);x++) {
  for (int y=0;MAX_P>y;y++) {
   dp[x][y] = INF;
   if (x==0) dp[x][y] = 0;
  }
 }
 memset(store,0,sizeof(store));
}

void spfa(int id) {
 d[id][id]=0;
 for (int x=0;MAX_N>x;x++) in_que[x]=false;
 queue<int> que;
 que.push(id);
 while (!que.empty()) {
  int t=que.front();
  que.pop();
  in_que[t]=false;
  for (auto i=edg[t].begin();i!=edg[t].end();i++) {
   int tmp = *i;
   if (d[id][tmp] > d[id][t] + w[t][tmp]) {
    d[id][tmp] = d[id][t] + w[t][tmp];
    if (in_que[tmp]==false) {
     que.push(tmp);
     in_que[tmp]=true;
    }
   }
  }
 }
}

int main () {
// freopen("output.txt","w",stdout);
 int T;
 scanf("%d",&T);
 while (T--) {
  init();
  int n,m;
  scanf("%d %d",&n,&m);
  for (int x=0;m>x;x++) {
   int i,j;
   int k,l;
   scanf("%d %d %d.%d",&i,&j,&k,&l);
   w[i][j] = min(w[i][j],k*100+l);
   w[j][i] = min(w[j][i],k*100+l);
   edg[i].push_back(j);
   edg[j].push_back(i);
  }
  int p;
  scanf("%d",&p);
  for (int x=0;p>x;x++) {
   int i;
   int j,k;
   scanf("%d %d.%d",&i,&j,&k);
   store[x]=i;
   cost[x]=j*100+k;
  }
  for (int x=0;n>=x;x++) spfa(x);
  for (int x=0;(1<<(p)) > x;x++) {
   for (int y=0;p>y;y++) {
    if ((x | (1<<y)) == x) {
     int tmp= (x ^ (1<<y));
     if (tmp==0) dp[x][y] = d[0][store[y]];
     else {
      for (int z=0;p>z;z++) {
       dp[x][y] = min(dp[x][y],dp[tmp][z] + d[store[z]][store[y]]);
      }
     }
    }
   }
  }
  int best = 0;
  for (int x=0;(1<<(p)) > x;x++) {
   for (int y=0;p>y;y++) {
//    cout<<"dp["<<x<<"]["<<y<<"] = "<<dp[x][y]<<endl;
    int tmp=0;
    //last = y
    for (int z=0;p>z;z++) {
     if (((1<<z) | x) == x) {
      tmp += cost[z];
     }
    }
//    cout << "x="<<x<<" , y="<<y<<" , tmp="<<tmp<<" , ";
//    cout<<"minus = "<<(dp[x][y] + d[store[y]][0])<<endl;
    tmp -= (dp[x][y] + d[store[y]][0]);
    
    best = max(best,tmp);
   }
  }
  if (best==0.0) puts("Don\'t leave the house");
  else printf("Daniel can save $%d.%02d\n",best/100,best%100);
 }
}