1 /** 2 * poj 3 * Problem#2449 4 * Accepted 5 * Time: 250ms 6 * Memory: 9252k 7 */ 8 #include <iostream> 9 #include <fstream> 10 #include <sstream> 11 #include <algorithm> 12 #include <cstdio> 13 #include <cstdlib> 14 #include <cstring> 15 #include <ctime> 16 #include <cctype> 17 #include <cmath> 18 #include <vector> 19 #include <queue> 20 #include <stack> 21 #include <map> 22 #include <set> 23 #include <bitset> 24 using namespace std; 25 typedef bool boolean; 26 27 typedef class Edge { 28 public: 29 int end; 30 int next; 31 int w; 32 33 Edge(int end = 0, int next = -1, int w = 0):end(end), next(next), w(w) { } 34 }Edge; 35 36 const int N = 1e3, M = 1e5; 37 38 typedef class MapManager { 39 public: 40 int cnt; 41 int h[N + 5]; 42 Edge edge[M + 5]; 43 44 MapManager() { } 45 MapManager(int n):cnt(-1) { 46 // h = new int[(n + 1)]; 47 // edge = new Edge[(m + 1)]; 48 memset(h, -1, sizeof(int) * (n + 1)); 49 } 50 51 inline void addEdge(int u, int v, int w) { 52 edge[++cnt] = (Edge(v, h[u], w)); 53 // h[u] = (signed)edge.size() - 1; 54 h[u] = cnt; 55 } 56 57 inline int start(int node) { return h[node]; } 58 59 Edge& operator [] (int pos) { 60 return edge[pos]; 61 } 62 }MapManager; 63 #define m_endpos -1 64 65 int n, m; 66 MapManager g; 67 MapManager rg; 68 int s, t, k; 69 int ds[N + 5]; 70 71 inline void init() { 72 scanf("%d%d", &n, &m); 73 memset(g.h, -1, sizeof(int) * (n + 1)); 74 memset(rg.h, -1, sizeof(int) * (n + 1)); 75 for(int i = 1, u, v, w; i <= m; i++) { 76 scanf("%d%d%d", &u, &v, &w); 77 g.addEdge(u, v, w); 78 rg.addEdge(v, u, w); 79 } 80 scanf("%d%d%d", &s, &t, &k); 81 // ds = new int[(n + 1)]; 82 } 83 84 #define g rg 85 #define f ds 86 #define que que1 87 boolean vis[N + 5]; 88 queue<int> que; 89 boolean spfa(int s, int t) { 90 memset(f, 0x7f, sizeof(int) * (n + 1)); 91 memset(vis, false, sizeof(boolean) * (n + 1)); 92 que.push(s); 93 f[s] = 0; 94 while(!que.empty()) { 95 int e = que.front(); 96 que.pop(); 97 vis[e] = false; 98 for(int i = g.start(e); i != m_endpos; i = g[i].next) { 99 int& eu = g[i].end; 100 // cout << e << " " << eu << " " << i <<endl; 101 if(f[e] + g[i].w < f[eu]) { 102 f[eu] = f[e] + g[i].w; 103 if(!vis[eu]) { 104 que.push(eu); 105 vis[eu] = true; 106 } 107 } 108 } 109 } 110 return (f[t] != 0x7f7f7f7f); 111 } 112 #undef g 113 #undef f 114 #undef que 115 116 typedef class Status { 117 public: 118 int node; 119 int dis; 120 int priority; 121 122 Status(int node = 0, int dis = 0):node(node), dis(dis), priority(h()) { } 123 124 int h() { 125 return dis + ds[node]; 126 } 127 128 boolean operator < (Status b) const { 129 return priority > b.priority; 130 } 131 }Status; 132 133 int label[N + 5]; 134 priority_queue<Status> que; 135 int bfs(int s, int t) { 136 if(s == t) k++; 137 // label = new int[(n + 1)]; 138 memset(label, 0, sizeof(int) * (n + 1)); 139 que.push(Status(s, 0)); 140 while(!que.empty()) { 141 Status e = que.top(); 142 que.pop(); 143 label[e.node]++; 144 if(e.node == t && label[e.node] == k) 145 return e.dis; 146 for(int i = g.start(e.node); i != m_endpos; i = g[i].next) { 147 if(label[g[i].end] < k) 148 que.push(Status(g[i].end, e.dis + g[i].w)); 149 } 150 } 151 return -1; 152 } 153 154 inline void solve() { 155 if(!spfa(t, s)) { 156 puts("-1"); 157 return; 158 } 159 printf("%d", bfs(s, t)); 160 } 161 162 int main() { 163 init(); 164 solve(); 165 return 0; 166 } 167 168 最短路算法 + A*
转载自 https://www.cnblogs.com/yyf0309/p/8438849.html