【POJ No. 2449】 第K 短路 Remmarguts‘ Date

【POJ No. 2449】 第K 短路 Remmarguts’ Date

POJ 题目地址

【题意】

给定一个有向图，N 个节点，M 条边。求从源点S 到终点T 的第K 短路。路径可能包含两次或两次以上的同一节点，甚至是S 或T 。具有相同长度的不同路径将被视为不同。

【输入输出】

输入：

第1行包含两个整数N 和M （1≤N ≤1000，0≤M ≤100000）。节点编号为1～N 。以下M 行中的每一行都包含3个整数A 、B和T （1≤A , B ≤N ，1≤T ≤100），表示从A 到B 有一条直达的路径，需要时间T 。最后一行包含3个整数S 、T 和K （1≤S , T ≤N ，1≤K ≤1000）。

输出：

单行输出第K 短路径的长度（所需时间）。如果不存在第K 短路，则输出-1。

【样例】

【思路分析】

这道题求第K 短路。

如果采用优先队列式广度优先搜索算法，则记录当前节点v 和源点s 到v 的最短路径长度(v , dist)。首先将(s , 0)入队，然后每次都从优先队列中取出dist最小的二元组(x ,dist)，对x 的每一个邻接点y 都进行扩展，将新的二元组(y , dist+w(x , y ))入队。第1次从优先队列中取出(x , dist)时，就得到从源点s 到x 的最短路径长度dist。那么在第i 次从优先队列中取出(x ,dist)时，就得到从源点s 到x 的第i 短路径长度dist。

实际上，从源点s 到当前节点x 的最短路径长度最小，并不代表经过x 就能够得到从源点s 到终点t 的最短路径长度。

因为余下的路有可能很长，并不知道从x 到终点t 的最短路径长度是多少。因此可以考虑采用A*算法，设置评估函数f (x )=g (x )+h (x )，其中g (x )表示从源点s 到节点x 的最短路径长度，h (x )表示从节点x 到终点t 的最短路径长度。将f (x )作为优先队列的优先级，f (x )越小，得到从起点到终点最短路径长度的可能性越大。

【算法设计】

① 在原图的反向图中，采用Dijkstra算法求出从终点t 到所有节点x 的最短路径长度dist[x ]。实际上，dist[x ]就是原图中从节点x 到终点t 的最短路径长度。

② 如果dist[s ]=inf，则说明从源点无法到达终点，返回-1，算法结束。

③ 在原图中，采用A*算法求解。用三元组(v , g , h )记录状态，第1个参数为当前节点编号，后两个参数分别代表从源点到当前节点的最短路径长度和从当前节点到终点的最短路径长度。优先级为g +h，其值越小，优先级越高。初始时，将(s , 0, 0)加入优先队列中。

④ 如果队列不空，则队头p 出队，u =p .v ，节点u 的访问次数加1，即times[u ]++。如果u 正好是终点且访问次数为k ，则返回最短路径长度p .g +p .h ，算法结束。

⑤ 如果times[u ]>k ，则不再扩展，否则扩展u 的所有邻接点E[i ].v ，将(E[i ].v , p .g +E[i ].w , dist[E[i ].v ])入队。

【算法实现】

#include
#include
#include
#include

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1005;
const int maxm=100005;

struct edge{
    int v,w,nxt;
}E[maxm],E2[maxm];
int cnt,head[maxn],cnt2,head2[maxn];

void add(int u,int v,int w){
	
    E[cnt].v=v;
    E[cnt].w=w;
    E[cnt].nxt=head[u];
    head[u]=cnt++;
    E2[cnt2].v=u;
    E2[cnt2].w=w;
    E2[cnt2].nxt=head2[v];
    head2[v]=cnt2++;
}

struct node{
	
    int v,d;
    node(){}
    node(int v,int d):v(v),d(d){}
    bool operator < (const node &b) const{
        return d>b.d;
    }
};

int n,m,k,dist[maxn];
bool vis[maxn];

void dijkstra(int s){
	
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    dist[s]=0;
    priority_queue<node> que;
    que.push(node(s,0));
    
    while(!que.empty()){
        node p=que.top();
        que.pop();
        int u=p.v;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head2[u];~i;i=E2[i].nxt){
            int v=E2[i].v,w=E2[i].w;
            if(!vis[v]&&p.d+w<dist[v]) {
                dist[v]=p.d+w;
                que.push(node(v,dist[v]));
            }
        }
    }
}

struct point{
	
    int v,g,h;
    point(){}
    point(int v,int g,int h):v(v),g(g),h(h){}
    bool operator < (const point & b) const{
        return g+h>b.g+b.h;
    }
    
};

int times[maxn];

int Astar(int s,int t){
	
    if(dist[s]==inf) return -1;
    memset(times,0,sizeof(times));
    priority_queue<point> Q;
    Q.push(point(s,0,0));
    
    while(!Q.empty()){
        point p=Q.top();
        Q.pop();
        int u=p.v;
        times[u]++;
        if(times[u]==k&&u==t)
            return p.g+p.h;
        if(times[u]>k)
            continue;
        for(int i=head[u];~i;i=E[i].nxt)
            Q.push(point(E[i].v,p.g+E[i].w,dist[E[i].v]));
    }
    return -1;
}

int main(){
	
    int u,v,w,s,t;
    scanf("%d%d",&n,&m);
    cnt=cnt2=0;
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    scanf("%d%d%d",&s,&t,&k);
    if(s==t)
        k++;
    dijkstra(t);
    printf("%d\n",Astar(s,t));
    
    return 0;
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120