Language:
Remmarguts' Date
| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 44482 | Accepted: 12303 |
Description
"Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.
Input
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).
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
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.
Sample Input
2 2 1 2 5 2 1 4 1 2 2
Sample Output
14
Source
POJ Monthly,Zeyuan Zhu
题意：给你一张有向图，希望你求出从节点s到t的第K短路
思路：估价函数的选取是根据反向图上根据dijstkra求出由t节点出发的最短路，所以该路径当前到终点的估值就被定义为已走过的路程+该节点到t的最短路径，每次在队列里取出估价最小的状态进行维护，需要注意的是一个节点被取出的次数不能大于K次，如果取出一个节点大于K次，那么从s到t肯定不会走当前的路径，因为总有最优的K条路是经过该节点1~k次到t；
Astar算法入门级题目，感觉Astar算法像是优先队列bfs+剪枝 ；
估价函数的设置，这个模板题是根据蓝书的思路自己慢慢敲的，感觉Astar算法的效率与估价函数的设置有很大关系 ；
他是在优先队列BFS的基础上加了些优化 。
ac代码如下
/*************************************************************************
> File Name: poj.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
> Created Time: 2020年11月17日 星期二 20时29分16秒
************************************************************************/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
const int N = 2e5+10,inf = 0x3f3f3f3f;
int n,m,k,l,t,s;
vector<int>S[N],H[N],val[N],eva[N];int dist[N];bool st[N];
void dij(){
memset(dist,inf,sizeof dist);
priority_queue<PII>G;
//memset(st,0,sizeof st);
dist[t] = 0;
G.push(mp(0,t));
while(!G.empty()){
int id = G.top().y,pr = -G.top().x;G.pop();
if(st[id]==true)continue;
st[id] = true;
for(int i=0;i<(int)H[id].size();++i){
int p = H[id][i];
if(val[id][i]+pr<dist[p]){
dist[p] = val[id][i]+pr;if(st[p]==false)
G.push(mp(-dist[p],p));
}
}
}
return;
}
int cnt[N];
int bfs(){
priority_queue<PII>G;
G.push(mp(-dist[s],s));
while(!G.empty()){
int id = G.top().y,pr =- G.top().x;
G.pop();cnt[id]++;
if(cnt[id]>k)continue;
if(id==t&&cnt[id]==k)return pr;
for(int i=0;i<(int)S[id].size();++i){
int p = S[id][i];if(cnt[p]>=k)continue;
G.push(mp(-(pr-dist[id]+dist[p]+eva[id][i]),p));
}
}
return -1;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){int a,b;
scanf("%d%d%d",&a,&b,&l);
H[b].pb(a);val[b].pb(l);S[a].pb(b);eva[a].pb(l);
}scanf("%d%d%d",&s,&t,&k);
if(m==0){
printf("-1\n");return;
}
dij();
printf("%d\n",bfs());
}
int main(){
solve();
return 0;
}
许可协议
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
分享文章
