POJ 2449 Remmarguts' Date
Time Limit: 4000MS | Memory Limit: 65536K | |
Total Submissions: 30725 | Accepted: 8389 |
Description
"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 last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
Sample Input
2 2
1 2 5
2 1 4
1 2 2
Sample Output
14
Source
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define M 100005
#define N 1005
using namespace std;
struct node
{
int to,f,g;
bool operator<(node a)const
{
if(f==a.f) return g>a.g;
return f>a.f;
}
};
struct Edge
{
int next,to,val;
};
Edge edge1[M*],edge2[M*];
int n,m,dist[N],head1[N],head2[N],cnt;
bool vis[N];
void spfa(int s)
{
queue<int>Q;
for(int i=;i<=n;++i) dist[i]=M,vis[i]=;
dist[s]=;
Q.push(s);
vis[s]=;
while(!Q.empty())
{
int now=Q.front();Q.pop();
vis[now]=;
for(int i=head2[now];i;i=edge2[i].next)
{
int v=edge2[i].to;
if(dist[v]>dist[now]+edge2[i].val)
{
dist[v]=dist[now]+edge2[i].val;
if(!vis[v])
{
vis[v]=;
Q.push(v);
}
}
}
}
}
inline void ins(int u,int v,int w)
{
edge1[++cnt].next=head1[u];
edge1[cnt].to=v;
edge1[cnt].val=w;
head1[u]=cnt;
edge2[cnt].next=head2[v];
edge2[cnt].to=u;
edge2[cnt].val=w;
head2[v]=cnt;
}
int Astar(int s,int t,int k)
{
priority_queue<node>Q;
if(s==t) k++;
int cnt=;
if(dist[s]==M) return -;
node a,tmp;
a.to=s;
a.g=;
a.f=a.g+dist[a.to];
Q.push(a);
while(!Q.empty())
{
node now=Q.top();Q.pop();
if(now.to==t) cnt++;
if(cnt==k) return now.g;
for(int i=head1[now.to];i;i=edge1[i].next)
{
int v=edge1[i].to;
tmp.to=v;
tmp.g=now.g+edge1[i].val ;
tmp.f=tmp.g+dist[tmp.to];
Q.push(tmp);
}
}
return -;
}
inline void init()
{
cnt=;
memset(head1,,sizeof(head1));
memset(head2,,sizeof(head2));
}
int main()
{
for(int s,t,k;cin>>n>>m;)
{
init();
for(int x,y,z;m--;)
{
cin>>x>>y>>z;
ins(x,y,z);
}
cin>>s>>t>>k;
spfa(t);
int ans=Astar(s,t,k);
cout<<ans<<endl;
}
return ;
}
最新文章
- 错误:媒体集有 2 个媒体簇,但只提供了 1 个 sql2005 备份错误。
- 苹果推送(APNs)ios push小结
- HTML+CSS小实战案例
- Hadoop概括——学习笔记<;一>;转
- 【字符串处理】HDOJ-1020-Encoding
- 初识SQL注入
- 一分钟搭建Webpack+react+es6框架
- Xcode中报错或警告信息整理,持续更新...
- 优化数据页面(18)——标注keyword
- 运营商网络採用SDN所面临的挑战(一)
- APUE 4 - 线程
- SpringCloud的应用发布(四)顺序启动各个应用
- [Swift]LeetCode338. 比特位计数 | Counting Bits
- ☆ [WC2006] 水管局长 「LCT动态维护最小生成树」
- 9Linux_LVM_iptables
- WPF Button 样式
- rtf格式 C#设置字间距 CharacterSpacing
- BCD码(如何转换,转换方式的证明)
- Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2) 【ABC】
- js时间加减
热门文章
- 获取access_token时却报出下列错误信息:{";errcode";:40164,";errmsg";:";invalid ip 61.172.68.219, not in whitelist hint: [KJZfAa0644e575]";},以及一些其他报错
- 自适应文案提示框、无数据图片加载<;IOS小组件>;
- TCPflow:在Linux中分析和调试网络流量的利器(转)
- 【Linux学习】Linux系统管理2—作业调度
- Axure RP 7.0 标准教程(2)--基本介绍
- sql添加表
- Lightoj 1067【逆元模板(求C(N,M))】
- Ogre 中使用OIS的两种模式
- euler证明
- Shiro 权限管理框架