谢谢dalao @[Fraciton](/space/show?uid=32107)
by y2823774827y @ 2018-10-02 21:53:24
@[y2823774827y](/space/show?uid=88804) 好吧我的问题，这个问题的A*估价函数太难写了...orz膜完就跑（即使加了记忆化也只有80分...）
by Fraction @ 2018-10-02 22:13:02
还是得再次感谢大佬，蒟蒻用结构体队列去维护，~~应该没错~~，已经AC了 @[Fraciton](/space/show?uid=32107)
by y2823774827y @ 2018-10-02 23:00:42
@[Fraciton](/space/show?uid=32107) 我写完了 A*，然后到了最优解第一页……
by LJC00118 @ 2018-10-21 13:57:32
@[LJC00118](/space/show?uid=51815) %%%能否私信看一看dalao的代码
by y2823774827y @ 2018-11-04 19:38:29
@[y2823774827y](/space/show?uid=88804) 不想私信啊
by LJC00118 @ 2018-11-04 20:10:35
@[y2823774827y](/space/show?uid=88804)
```cpp
#include <bits/stdc++.h>
#define CIOS ios::sync_with_stdio(false);
#define For(i, a, b) for(register int i = a; i <= b; i++)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
template <typename _T>
inline void read(_T &f) {
f = 0; _T fu = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}
while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}
f *= fu;
}
template <typename T>
void print(T x) {
if(x < 0) putchar('-'), x = -x;
if(x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
print(x); putchar(t);
}
const int N = 1e4 + 5, M = 2e5 + 5;
struct Edge {
int u, v, next, val;
}G[M];
int head[N], x[M], y[M], z[M];
int n, m, tot;
inline void addedge(int u, int v, int val) {
G[++tot] = (Edge) {u, v, head[u], val}, head[u] = tot;
}
int E[N];
void bfs(int *E, int s) {
memset(E, -1, N * 4);
queue <int> q; q.push(s); E[s] = 0;
// cerr << E[N - 1] << endl;
while(!q.empty()) {
int u = q.front(); q.pop();
for(register int i = head[u]; i; i = G[i].next) {
int v = G[i].v;
if(E[v] == -1) {
E[v] = E[u] + 1;
q.push(v);
}
}
}
// fprintf(stderr, "DEBUG_bfs >>> ");
// for(register int i = 1; i <= n; i++) fprintf(stderr, "%d ", E[i]);
// fprintf(stderr, "\n");
}
int dis[N];
void dij(int *dis, int s) {
memset(dis, 0x3f, N * 4);
priority_queue < pair <int, int> > Q;
dis[s] = 0; Q.push(make_pair(0, s));
while(!Q.empty()) {
pair <int, int> t = Q.top(); Q.pop();
if(-t.first > dis[t.second]) continue;
for(register int i = head[t.second]; i; i = G[i].next) {
int v = G[i].v;
if(dis[v] > dis[t.second] + G[i].val) {
dis[v] = dis[t.second] + G[i].val;
Q.push(make_pair(-dis[v], v));
}
}
}
}
struct ele {
int dis, E, now, u;
vector <int> ans;
ele () {ans.clear();}
ele (int a, int b, int c, int d) : dis(a), E(b), now(c), u(d) {ans.clear();}
bool operator < (const ele A) const {return now > A.now;}
};
priority_queue <ele> Q;
int calc1(int x) {return x * (x + 1) / 2;}
int calc(int dis, int E, int _dis, int _E) {
return dis + _dis - calc1(E - 1) + calc1(_E + E - 1);
}
const int INF = 0x7fffffff;
vector <int> Ans;
vector <int> :: iterator it;
int ans = INF;
void A_star(int s) {
ele u = ele(0, 0, calc(0, 0, dis[s], E[s]), s); u.ans.push_back(1); Q.push(u);
while(!Q.empty()) {
ele t = Q.top(); Q.pop();
// fprintf(stderr, "DEBUG >>> %d %d %d %d\n", t.u, t.dis, t.E, t.now);
if(t.now >= ans) return;
if(t.u == n) {
ans = t.dis;
Ans = t.ans;
return;
}
int u = t.u;
for(register int i = head[u]; i; i = G[i].next) {
int v = G[i].v;
ele Ans = ele(t.dis + G[i].val + t.E, t.E + 1, calc(t.dis + G[i].val + t.E, t.E + 1, dis[v], E[v]), v);
Ans.ans = t.ans; Ans.ans.push_back(v); Q.push(Ans);
}
}
}
int main() {
read(n); read(m);
for(register int i = 1; i <= m; i++) {
int a, b, c;
read(a); read(b); read(c);
x[i] = a; y[i] = b; z[i] = c;
addedge(b, a, c);
}
bfs(E, n); dij(dis, n); tot = 0;
memset(head, 0, sizeof(head));
for(register int i = 1; i <= m; i++) addedge(x[i], y[i], z[i]);
A_star(1); print(ans, '\n');
for(it = Ans.begin(); it != Ans.end(); it++) print(*it, ' ');
return 0;
}
```
by LJC00118 @ 2018-11-04 20:10:56
@[y2823774827y](/space/show?uid=88804) 正着反着都跑一遍取最小值对不对鸭qwq
by 阿蒙 @ 2018-11-05 07:59:27
%%%
by Earth执剑人罗辑 @ 2019-04-16 18:30:18
还有这一组
```cpp
IN
6 6
1 2 2
2 3 2
3 4 5
4 5 3
5 6 2
3 5 11
OUT
23
1 2 3 5 6
```
by 地表最强男人 @ 2019-09-19 15:16:28