Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

贴一个《挑战程序设计竞赛》风格的源码

Posted by vjubge4 at 2019-04-06 09:44:41 on Problem 2449
```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int oo = 0x3f3f3f3f;
struct Node{
int v, h, g;
bool operator < (const Node & a) const {
return a.g + a.h < g + h;
}
};

struct edge{
int to, cost;
};

vector<edge> G1[1000];
vector<edge> G2[1000];
int dist[1000];
int V, M, K;
int S,E;

void dijkstra(int s){
priority_queue<P, vector<P>, greater<P> > que;
memset(dist, oo, sizeof(dist));
dist[s] = 0;
que.push(P(0,s));
while (!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if (dist[v] < p.first)
continue;
for (int i = 0; i < G2[v].size(); ++i) {
edge e = G2[v][i];
if (dist[e.to] > dist[v] + e.cost){
dist[e.to] = dist[v] + e.cost;
que.push(P(dist[e.to], e.to));
}
}
}
}

int times[1000];
int Astar(int s, int e){
if (dist[s] == oo){
return -1;
}
memset(times, 0, sizeof(times));
priority_queue<Node> que;
que.push((Node){s, 0, 0});
while (!que.empty()){
Node p = que.top();
que.pop();
times[p.v] ++;
if (p.v == e && times[p.v] == K){
return p.h;
}
if (times[p.v] > K){
continue;
}
for (int i = 0; i < G1[p.v].size(); ++i) {
que.push((Node){G1[p.v][i].to, p.h + G1[p.v][i].cost, dist[G1[p.v][i].to]});
}
}
return -1;
}

int main(){
scanf("%d %d", &V, &M);
int a,b,c;
for (int i = 0; i < M; ++i) {
scanf("%d %d %d", &a, &b, &c);
G1[a-1].push_back((edge) {b-1, c});
G2[b-1].push_back((edge) {a-1, c});
}
scanf("%d %d %d", &S, &E, &K);
S--; E--;
if (S == E){
K++;
}
dijkstra(E);
printf("%d\n", Astar(S, E));
return 0;
}```

Followed by: