POJ 2449 Remmarguts' Date
http://poj.org/problem?id=2449
算法核心：A*、dijkstra
大意：求有向图中从s到t的k短路
分析:
1.用dijkstra逆向计算出所有点到t的最短距离dis[i]
2.建立估价函数 f(i)= g(i)+h(i)
其中g(i)为从s到i的实际距离，h(i)为从i到t的最短路dis[i]
3.使用上述估计函数用A*算法从s点出发BFS全图，用visited[i]表示点i的出队次数。
当visited[i]=k时，即找到从s到t的k短路为f(i)
其间若visited[i]>k则放弃该点
4.注意：若s==t,需 k+1;
View Code
#include
<
stdio.h
>
#include < string .h >
#include < queue >
using namespace std;
const int N = 1000 + 1 ;
const int M = 100000 + 1 ;
struct Edge
{
int from,to;
int dis;
Edge * next;
} * ed[N],edge[M], * re[N],redge[M];
int ednum;
int dis[N];
int visited[N];
void init( int n)
{
int i;
for (i = 0 ;i < n;i ++ )
{
ed[i] = NULL;
re[i] = NULL;
}
}
void addEdge( int from, int to, int dis)
{
Edge * ptr = & edge[ednum];
ptr -> from = from;
ptr -> to = to;
ptr -> dis = dis;
ptr -> next = ed[from];
ed[from] = ptr;
}
void addRedge( int from, int to, int dis)
{
Edge * ptr = & redge[ednum];
ptr -> from = from;
ptr -> to = to;
ptr -> dis = dis;
ptr -> next = re[from];
re[from] = ptr;
}
struct dnode // dijkstra()优先队列中使用的节点
{
int v,len; // 记录从出发点到节点v的长度
bool operator < ( const dnode & A) const
{
return A.len < len;
}
};
void dijkstra( int s, int n) // 计算各点到终点的距离
{
memset(visited, 0 , sizeof (visited));
memset(dis, - 1 , sizeof (dis));
priority_queue < dnode > Q;
dnode cur,next;
cur.len = 0 ;
cur.v = s;
Q.push(cur);
dis[s] = 0 ;
int vnum = 0 ; // 已访完的节点数
while ( ! Q.empty())
{
cur = Q.top();
Q.pop();
if (visited[cur.v]) continue ;
visited[cur.v] = 1 ;
vnum ++ ;
if (vnum == n) return ;
for (Edge * ed = re[cur.v];ed != NULL;ed = ed -> next)
{
if (visited[ed -> to] == 0 )
{
if (dis[ed -> to] ==- 1 || dis[ed -> to] > cur.len + ed -> dis)
{
next.len = cur.len + ed -> dis;
dis[ed -> to] = next.len;
next.v = ed -> to;
Q.push(next);
}
}
}
}
}
struct anode // astar()优先队列中的节点
{
int to; // 记录从出发点到当前节点的距离
int len;
bool operator < ( const anode & A) const
{
if (dis[A.to] ==- 1 ) return false ;
if (dis[to] ==- 1 ) return true ;
return A.len + dis[A.to] < len + dis[to]; // 估计函数的使用
}
};
int aStar( int from, int to, int k)
{
memset(visited, 0 , sizeof (visited));
priority_queue < anode > Q;
anode cur,next;
if (from == to)k ++ ; // 两点重合时按题意加1
cur.len = 0 ;
cur.to = from;
Q.push(cur);
while ( ! Q.empty())
{
cur = Q.top();
// printf("%d\n",cur.len);
Q.pop();
if (visited[cur.to] == k) return cur.len + dis[cur.to];
if (visited[cur.to] > k) continue ;
visited[cur.to] ++ ;
if (visited[to] == k) return cur.len;
for (Edge * ptr = ed[cur.to];ptr;ptr = ptr -> next)
{
next.len = cur.len + ptr -> dis;
next.to = ptr -> to;
Q.push(next);
}
}
return - 1 ;
}
int main()
{
int n,m;
while (scanf( " %d%d " , & n, & m) != EOF)
{
init(n);
ednum = 0 ;
while (m -- )
{
int a,b,t;
scanf( " %d%d%d " , & a, & b, & t);
a -- ;
b -- ;
addEdge(a,b,t);
addRedge(b,a,t);
ednum ++ ;
}
int s,t,k;
scanf( " %d%d%d " , & s, & t, & k);
s -- ,t -- ;
dijkstra(t,n);
// for(int i=0;i<n;i++)
// printf("%d\n",dis[i]);
if (dis[s] ==- 1 )printf( " -1\n " );
else
printf( " %d\n " ,aStar(s,t,k));
}
return 0 ;
}
#include < string .h >
#include < queue >
using namespace std;
const int N = 1000 + 1 ;
const int M = 100000 + 1 ;
struct Edge
{
int from,to;
int dis;
Edge * next;
} * ed[N],edge[M], * re[N],redge[M];
int ednum;
int dis[N];
int visited[N];
void init( int n)
{
int i;
for (i = 0 ;i < n;i ++ )
{
ed[i] = NULL;
re[i] = NULL;
}
}
void addEdge( int from, int to, int dis)
{
Edge * ptr = & edge[ednum];
ptr -> from = from;
ptr -> to = to;
ptr -> dis = dis;
ptr -> next = ed[from];
ed[from] = ptr;
}
void addRedge( int from, int to, int dis)
{
Edge * ptr = & redge[ednum];
ptr -> from = from;
ptr -> to = to;
ptr -> dis = dis;
ptr -> next = re[from];
re[from] = ptr;
}
struct dnode // dijkstra()优先队列中使用的节点
{
int v,len; // 记录从出发点到节点v的长度
bool operator < ( const dnode & A) const
{
return A.len < len;
}
};
void dijkstra( int s, int n) // 计算各点到终点的距离
{
memset(visited, 0 , sizeof (visited));
memset(dis, - 1 , sizeof (dis));
priority_queue < dnode > Q;
dnode cur,next;
cur.len = 0 ;
cur.v = s;
Q.push(cur);
dis[s] = 0 ;
int vnum = 0 ; // 已访完的节点数
while ( ! Q.empty())
{
cur = Q.top();
Q.pop();
if (visited[cur.v]) continue ;
visited[cur.v] = 1 ;
vnum ++ ;
if (vnum == n) return ;
for (Edge * ed = re[cur.v];ed != NULL;ed = ed -> next)
{
if (visited[ed -> to] == 0 )
{
if (dis[ed -> to] ==- 1 || dis[ed -> to] > cur.len + ed -> dis)
{
next.len = cur.len + ed -> dis;
dis[ed -> to] = next.len;
next.v = ed -> to;
Q.push(next);
}
}
}
}
}
struct anode // astar()优先队列中的节点
{
int to; // 记录从出发点到当前节点的距离
int len;
bool operator < ( const anode & A) const
{
if (dis[A.to] ==- 1 ) return false ;
if (dis[to] ==- 1 ) return true ;
return A.len + dis[A.to] < len + dis[to]; // 估计函数的使用
}
};
int aStar( int from, int to, int k)
{
memset(visited, 0 , sizeof (visited));
priority_queue < anode > Q;
anode cur,next;
if (from == to)k ++ ; // 两点重合时按题意加1
cur.len = 0 ;
cur.to = from;
Q.push(cur);
while ( ! Q.empty())
{
cur = Q.top();
// printf("%d\n",cur.len);
Q.pop();
if (visited[cur.to] == k) return cur.len + dis[cur.to];
if (visited[cur.to] > k) continue ;
visited[cur.to] ++ ;
if (visited[to] == k) return cur.len;
for (Edge * ptr = ed[cur.to];ptr;ptr = ptr -> next)
{
next.len = cur.len + ptr -> dis;
next.to = ptr -> to;
Q.push(next);
}
}
return - 1 ;
}
int main()
{
int n,m;
while (scanf( " %d%d " , & n, & m) != EOF)
{
init(n);
ednum = 0 ;
while (m -- )
{
int a,b,t;
scanf( " %d%d%d " , & a, & b, & t);
a -- ;
b -- ;
addEdge(a,b,t);
addRedge(b,a,t);
ednum ++ ;
}
int s,t,k;
scanf( " %d%d%d " , & s, & t, & k);
s -- ,t -- ;
dijkstra(t,n);
// for(int i=0;i<n;i++)
// printf("%d\n",dis[i]);
if (dis[s] ==- 1 )printf( " -1\n " );
else
printf( " %d\n " ,aStar(s,t,k));
}
return 0 ;
}