SGU 145 Strange People (recommended)

K短『簡單』路!!!!!!!! NPC問題，使用暴搜～

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

通常IDA*都是用在解一些奇怪的題目上面

像是8 puzzle, 加法鏈…等等

而且都是一層一層加深所謂的 step，藉此作為他的limit

但是這邊這題，卻是透過二分搜距離來創造他的limit

而H函數則是透過dijkstra做一次到終點的最短距離來的

這樣不會太慢嘛？因為在之前的step當中，只要小小的增加一次

可到達的種類數就會陡然的暴增

但是這一題，因為你只要走到終點K次

你就知道這是一個大於等於答案的解，於是便可以直接return回去

所以limit太大時，種類數並不會暴增，反而更可以加快return回去的速度

反而是太小的時候才較為糟糕（我一開始一直沒搞清楚）

而在太小的時候，又可以不斷的利用啟發式函數做減枝，綜合起來

整題速度還算挺可以的（但SGU說實在，測資貌似還挺水的）

//By momo
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 110
#define INF 999999999
#define MP make_pair
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;
typedef pair<int,int> PII;

int n, m, k, s, t, dis[N];
priority_queue<PII> que;

struct edge{
    int t, c;
    edge(){}
    edge(int _t,int _c){t=_t,c=_c;}
};
vector<edge> G[N];

int vst[N], cnt = 0, vs[N], vn, bomb, pnt;
void dfs(int p, int cst, int lmt)
{
    if(cst+dis[p] > lmt) return;
    if(p == t){
        cnt++;
        if(bomb && cst == lmt){
            pnt = 1;
            printf("%d %d\n", lmt, vn);
            for(int i = 0; i < vn; i++)
                printf("%d%c", vs[i], i == vn-1?'\n':' ');
        }
        return;
    }
    FOR(it, G[p]){
        if(!vst[it->t]){
            vst[it->t] = 1;
            vs[vn++] = it->t;
           
            dfs(it->t, cst+it->c, lmt);
           
            vst[it->t] = 0;
            vn--;
           
            if(pnt || cnt == k) return;
        }
    }
}

bool check(int lmt)
{
    fill(vst+1, vst+n+1, 0);
    vst[s] = 1; cnt = 0;
    vs[vn = 0] = s; vn++;
    dfs(s, 0, lmt);
    return cnt == k;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a].push_back(edge(b, c));
        G[b].push_back(edge(a, c));
    }
    scanf("%d%d", &s, &t);

    //dijkstra
    for(int i = 1; i <= n; i++) dis[i] = INF;
    que.push(MP(dis[t] = 0, t));
    while(!que.empty()){
        PII now = que.top(); que.pop();
        int p = now.second;
        if(dis[p] < -now.first) continue;
        FOR(it, G[p]){
            if(dis[it->t] > dis[p]+it->c){
                dis[it->t] = dis[p]+it->c;
                que.push(MP(-dis[it->t], it->t));
            }
        }
    }

    int lb = -1, rb = INF;
    while(lb != rb-1){
        int mid = (lb+rb) >> 1;
        bomb = 1;
        if(check(mid)) rb = mid;
        else lb = mid;
    }
    bomb = 1;
    check(rb);
}