静态链表实现图存储#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int INF = 1e8;
const int NUMV = 1200;//number of vertex
const int NUME = 120010;//number of edge
int head[NUMV];
int ux[NUME], vx[NUME];//edge: ux->vx
int next[NUME], cost[NUME];
int instk[NUMV];//in stack or not
int dist[NUMV]; //shortest distance from dest to each vertex
int cnt[NUMV]; //count the times of a node out of queue
int n, m;
int s, t, k;
struct Node {
int f, g;//f = g + h
int v;
Node(int a, int b, int c):f(a),g(b),v(c){}
bool operator < (const Node& a)const {
return a.f < f;
}
};
int spfa(int s, int t, int vx[]) {
stack<int> stk;
//initial instk[] and dist[]
for (int i = 0; i <= n; ++i) {
instk[i] = 0;
dist[i] = INF;
}
//push s into the stack
dist[s] = 0;
instk[s] = 1;
stk.push(s);
while (!stk.empty()) {
int cur = stk.top();
stk.pop();
instk[cur] = 0;
for (int i = head[cur]; i >= 0; i = next[i]) {
if (dist[cur]+cost[i] < dist[vx[i]]) {
dist[vx[i]] = dist[cur]+cost[i];
if (!instk[vx[i]]) {
stk.push(vx[i]);
instk[vx[i]] = 1;
}
}
}
}
if (dist[t] == INF) return 0;
else return 1;
}
/*
int q[NUMV];
void Spfa(int s,int t, int vx[])
{
int i,u,v,l,r=0,tmp;
for(i=0;i<=n;++i)dist[i]=INF,instk[i]=0;
dist[s]=0;
q[r++]=s;
for(l=0;l<r;++l)
for(i=head[u=q[l]],instk[u]=0;i>=0;i=next[i])
if((tmp=dist[u]+cost[i])<dist[v=vx[i]])
{
dist[v]=tmp;
if(instk[v])continue;
instk[q[r++]=v]=1;
}
}
*/
int A_star(int s, int t, int vx[]) {
if (dist[s] >= INF) return -1;
for (int i = 0; i <= n; ++i) cnt[i] = 0;
priority_queue<Node> nodeq;
nodeq.push(Node(dist[s],0,s));
while (!nodeq.empty()) {
Node cur = nodeq.top();
nodeq.pop();
++cnt[cur.v];
if (cnt[cur.v] > k) continue;
if (cnt[t] == k) return cur.f;
for (int i = head[cur.v]; i >= 0; i = next[i]) {
int g = cur.g + cost[i];
int f = g + dist[vx[i]];
int v = vx[i];
nodeq.push(Node(f,g,v));
}
}
return -1;
}
int main(void)
{
while (scanf("%d %d", &n, &m) == 2) {
memset(head, -1, sizeof(head));
for (int i = 0; i < m; ++i) {
scanf("%d %d %d", ux+i, vx+i, cost+i);
next[i] = head[vx[i]];
head[vx[i]] = i;
}
scanf("%d %d %d", &s, &t, &k);
if (s == t) k += 1;
spfa(t, s, ux);
memset(head, -1, sizeof(head));
for (int i = 0; i < m; ++i) {
next[i] = head[ux[i]];
head[ux[i]] = i;
}
printf("%d\n", A_star(s, t, vx));
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int INF = 1e8;
const int NUMV = 1010;
const int NUME = 100010;
struct Node {
int f, g;
int v;
Node (int a, int b, int c):f(a),g(b),v(c) {}
bool operator < (const Node& a) const {
return a.f < f;
}
};
struct Edge {
int u, v;//from u to v
int w;//cost
};
vector<Edge> edges;
vector<int> G[NUMV];
vector<int> iG[NUMV];//inverse graph
int dist[NUMV];//shotest distance
int instk[NUMV];//in stack :spfa
int n, m;
int s, t, k;
void add_edge(vector<int> G[], int u, int v, int w) {
edges.push_back((Edge){u,v,w});
int m = edges.size();
G[u].push_back(m-1);
}
void spfa(int s, int t, vector<int> G[])
{
stack<int> stk;
for (int i = 0; i < n; ++i) {
dist[i] = INF;
instk[i] = 0;
}
dist[s] = 0;
stk.push(s);
instk[s] = 1;
while (!stk.empty()) {
int u = stk.top();
stk.pop();
instk[u] = 0;
for (int i = 0; i < G[u].size(); ++i) {
Edge& e = edges[G[u][i]];
if (dist[u]+e.w < dist[e.v]) {
dist[e.v] = dist[u]+e.w;
if (!instk[e.v]) {
stk.push(e.v);
instk[e.v] = 1;
}
}
}
}
}
int A_star(int s, int t, vector<int> G[]) {
if (dist[s] >= INF) return -1;
priority_queue<Node> nodeq;
nodeq.push(Node(dist[s], 0, s));
int cnt = 0;
while (!nodeq.empty()) {
Node cur = nodeq.top();
nodeq.pop();
if (cur.v == t) ++cnt;
if (cnt == k) return cur.f;
for (int i = 0; i < G[cur.v].size(); ++i) {
Edge &e = edges[G[cur.v][i]];
int v = e.v;
int g = cur.g + e.w;
int f = g + dist[v];
nodeq.push(Node(f, g, v));
}
}
return -1;
}
void clear() {
for (int i = 0; i < n; ++i) {
G[i].clear();
iG[i].clear();
}
edges.clear();
}
int main(void)
{
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 0; i < m; ++i) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(G, u, v, w);
add_edge(iG, v, u, w);
}
scanf("%d %d %d", &s, &t, &k);
spfa(t, s, iG);
if (s == t) ++k;
printf("%d\n", A_star(s, t, G));
clear();
}
return 0;
}
posted on 2013-01-14 18:23
lixiucheng 阅读(861)
评论(0) 编辑 收藏 引用