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

## 为什么MLE!?请教各位！

Posted by joeylee97 at 2017-08-14 14:18:41 on Problem 2449
```#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 100002
#define N 1009
#define INF 1000000009
#define eps 0.00000001
/*

1.将所有边反向建一个反图，然后求终点到各店的最短距离
2.优先队列 A*算法 每出队一个元素 cnt[cur]++

*/
struct edge
{
int to, cost, nxt;
}E[MAXN * 2];
struct node
{
int g, h, pos;//g是当前点到源点的距离估值 h是当前点到终点的距离估值
bool operator<(const node& rhs) const
{
return g + h < (rhs.g + rhs.h);
}
};
int n, m, from, to, lowcost[N], cnt = 0;
void addedge(int u, int v, int w)
{
E[cnt].to = v;
E[cnt].cost = w;

E[cnt].to = u;
E[cnt].cost = w;
}
void Dijkstra()
{
int vis[N];
memset(vis, 0, sizeof(vis));
memset(lowcost, INF, sizeof(lowcost));
lowcost[to] = 0;
for (int i = 0; i < n; i++)
{
int Minc = INF, k = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && lowcost[j] < Minc)
Minc = lowcost[j], k = j;
}
vis[k] = true;
for (int j = head2[k]; j != -1; j = E[j].nxt)
{
int v = E[j].to, w = E[j].cost;
if (!vis[v] && lowcost[v] > lowcost[k] + w)
{
lowcost[v] = lowcost[k] + w;
}
}
}
}
int Astar(int k)
{
int num[N];
memset(num, 0, sizeof(num));
node tmp, f;
priority_queue<node> q;
tmp.g = 0;
tmp.h = lowcost[from];
tmp.pos = from;
q.push(tmp);
while (!q.empty())
{
f = q.top();
q.pop();
num[f.pos]++;
if (num[f.pos] > k)
continue;
if (num[to] == k)
return f.g;
for (int i = head1[f.pos]; i != -1; i = E[i].nxt)
{
int v = E[i].to;
tmp.pos = v;
tmp.g = f.g + E[i].cost;
tmp.h = lowcost[v];
q.push(tmp);
}
}
return -1;
}
int main()
{
int a, b, c, k;
while (scanf("%d%d", &n, &m) != EOF)
{
cnt = 0;
for (int i = 0; i < m; i++)
scanf("%d%d%d", &a, &b, &c), addedge(a, b, c);
scanf("%d%d%d", &from, &to, &k);
if (from == to)
k++;
Dijkstra();
printf("%d\n", Astar(k));
}
return 0;
} ```

Followed by: