[TIOJ] 1255 砲打皮皮3

LINK：http://tioj.infor.org/problems/1255
　　看到這題很容易就想到TIOJ1014打地鼠那一題，然後就像我一樣完全用那題的方法刻，最後就在TIOJ上刷出了一排排光輝的WA歷史了QQ
　　其實也就只有一個地方不一樣，打地鼠那裏有說過可以將dp[0][0]當作起始值去做，但現在變成二維的就不行了，因為dp[0][0]是基於和p[0]的距離，但有可能有的點的x或y座標比p[0]更小，然後就會爛掉，其餘的都和打地鼠那一題差不多吧~~
　　複雜度：O(m^2*2^m)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
#define INF 999999999
#define endl '\n'
#define pb push_back
#define mt make_tuple
#define F first
#define S second
#define all(v) begin(v),end(v)
#define sz(v) (int)((v).size())
#define eps 1e-9
#define mod 1e9+7 
#define jizz ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(args...){string _s = #args; replace(all(_s),',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); error(_it,args);}
bool is_debug = 1;
void error(istream_iterator<string> _it)
{
    if(is_debug) cerr << endl;
}
template<typename T,typename... Args>
void error(istream_iterator<string> it,T a, Args... args)
{
    if(is_debug)
    {
        cerr << *it << " = " << a << "   ";
        error(++it,args...);
    }
}
inline int dis(PII a,PII b = {1,1})
{
    return abs(a.F-b.F)+abs(a.S-b.S);
}
int n,m,t[20],dp[(1<<18)][20],ans;
PII p[20];
int main()
{
    while(cin >> n >> m && n && m)
    {
        for(int i = 0; i < m; i++) cin >> p[i].F >> p[i].S >> t[i];
        fill(&dp[0][0],&dp[(1<<m)][m],INF); ans = INF;
        for(int s = 1,i = 0; s < (1<<m); s <<= 1,i++)
            dp[s][i] = ceil((double)dis(p[i])/t[i])*t[i];
        for(int s = 1; s < (1<<m); s++)
            for(int i = 0; i < m; i++)
            {
                if(!(s&(1<<i))) continue;
                for(int j = 0; j < m; j++)
                {
                    int d = dp[s-(1<<i)][j] + dis(p[j],p[i]);
                    int p = ceil((double)d/t[i])*t[i];
                    dp[s][i] = min(dp[s][i],p);
                }
                if(s == (1<<m)-1) ans = min(ans,dp[s][i]);
            }
        cout << ans << endl;
    }   
}