POJ2449 Remmarguts' Date
"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
<= 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).
Output
(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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long lol;
struct Node
{
int next,to;
lol dis;
}edge1[],edge2[];
int num1,num2,head1[],head2[];
lol dist[],ans,inf;
int S,T,k,tot,n,m;
bool vis[];
struct ZYYS
{
lol now,h;
int id;
bool operator <(const ZYYS &b)
const
{
if (h==b.h) return now>b.now;
return h>b.h;
}
};
void add1(int u,int v,lol d)
{
num1++;
edge1[num1].next=head1[u];
head1[u]=num1;
edge1[num1].to=v;
edge1[num1].dis=d;
}
void add2(int u,int v,lol d)
{
num2++;
edge2[num2].next=head2[u];
head2[u]=num2;
edge2[num2].to=v;
edge2[num2].dis=d;
}
void SPFA()
{int i;
queue<int>Q;
memset(dist,/,sizeof(dist));
inf=dist[];
Q.push(S);
dist[S]=;
while (Q.empty()==)
{
int u=Q.front();
Q.pop();
vis[u]=;
for (i=head1[u];i;i=edge1[i].next)
{
int v=edge1[i].to;
if (dist[v]>dist[u]+edge1[i].dis)
{
dist[v]=dist[u]+edge1[i].dis;
if (vis[v]==)
{
vis[v]=;
Q.push(v);
}
}
}
}
}
void Astar()
{int i;
if (S==T) k++;
priority_queue<ZYYS>Q;
ZYYS tmp;
if (dist[T]==inf) return;
tmp.id=T;tmp.now=;tmp.h=dist[T];
Q.push(tmp);
while (Q.empty()==)
{
tmp=Q.top();
Q.pop();
if (tmp.id==S)
{
++tot;
if (tot==k)
{
ans=tmp.now;
return;
}
}
for (i=head2[tmp.id];i;i=edge2[i].next)
{
int v=edge2[i].to;
ZYYS to;
to.id=v;
to.now=tmp.now+edge2[i].dis;
to.h=to.now+dist[v];
Q.push(to);
}
}
}
int main()
{int i,u,v;
lol d;
cin>>n>>m;
for (i=;i<=m;i++)
{
scanf("%d%d%lld",&u,&v,&d);
add1(u,v,d);
add2(v,u,d);
}
cin>>S>>T>>k;
SPFA();
Astar();
if (tot!=k) printf("-1");
else
cout<<ans;
}
最新文章
- android中webview调用拨号盘
- C#中获取当前时间:System.DateTime.Now.ToString()用法
- Laravel4中的Validator
- springmvc__SimpleUrlHandlerMapping(对访问地址进行加工,以键值对的形式)
- MySql和SQL Server数据类型 对比
- 配置普通用户可以运行saltstack的模块
- 转换 Html 内容为纯文本内容(html,文本互转)
- Maven入门1-在Eclipse中新建Maven Web项目
- 【批处理】IF ERRORLEVER语句顺序注意
- hdu:2036.改革春风吹满地
- 102. Binary Tree Level Order Traversal二叉树层序遍历
- Ability
- 【清北学堂2018-刷题冲刺】Contest 2
- Mysql临时文件目录控制
- MVC模式的原理
- ida自动编译配置
- GeoHash解析及java实现
- SharePoint BDC(Business Data Connectivity)服务-PowerShell
- 【转】Twitter Storm: 在生产集群上运行topology
- 【洛谷】【动态规划(多维)】P1006 传纸条