POJ - 2449 Remmarguts' Date（ K短路 Astar ）

传送门：AcWing - 180

题目描述

求第K短路

输入描述

The first line contains two integer numbers $N$ and $M$ $(1 <= N <= 1000, 0 <= M <= 100000)$. Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers $A$, $B$ and $T$ $(1 <= A, B <= N, 1 <= T <= 100)$. It shows that there is a directed sideway from A-th station to B-th station with time T.

The last line consists of three integer numbers $S$, $T$ and $K$ $(1 <= S, T <= N, 1 <= K <= 1000)$.

输出描述

A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output “-1” (without quotes) instead.

思路分析

有向图求第K短路，先用dij或spfa跑出终点的估价值，再用A-star

样例输入

2 2
1 2 5
2 1 4
1 2 2

样例输出

14

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1010;

int n,m;
int dis[N];
vector<pair<int,int>>e[N],re[N];

struct A{
    int v,val;
    friend bool operator < (A x,A y) {
        return x.val+dis[x.v]>y.val+dis[y.v];
    }
};


inline void dij(int s){
    priority_queue< pair<int,int> > q;
    mem(dis,INF);
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int u=q.top().se;
        q.pop();
        for(auto i:re[u]){
            int v=i.fi,w=i.se;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
    
}

inline int Astar(int s,int t,int k){
    priority_queue<A>q;
    int cnt=0;
    A tem;
    tem.v=s;
    tem.val=0;
    q.push(tem);
    while(!q.empty()){
        A u=q.top();
        q.pop();
        if(u.v==t)
            cnt++;
        if(cnt==k)
            return u.val;
        for(auto i:e[u.v]){
            tem.v=i.fi;
            tem.val=u.val+i.se;
            q.push(tem);
        }
    }
    return -1;
}


int main() {
    scanf("%d %d",&n,&m);
    while(m--){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        e[u].pb(make_pair(v,w));
        re[v].pb(make_pair(u,w));
    }
    int s,t,k;
    scanf("%d %d %d",&s,&t,&k);
    if(s==t)k++;
    dij(t);
    printf("%d\n",Astar(s,t,k));
    

    return 0;
}