- 晴天小猪历险记之Hill
-
fsxgc LV 8 @ 2016-11-12 11:30:38
内存只用了5000k啊
编译成功
foo.cpp: In function 'void dijkstra(int)':
foo.cpp:58:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<G[h.u].size(); i++)
^
测试数据 #0: RuntimeError, time = 15 ms, mem = 5564 KiB, score = 0
测试数据 #1: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #2: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #3: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #4: RuntimeError, time = 15 ms, mem = 5560 KiB, score = 0
测试数据 #5: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #6: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #7: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
测试数据 #8: RuntimeError, time = 15 ms, mem = 5564 KiB, score = 0
测试数据 #9: RuntimeError, time = 0 ms, mem = 5564 KiB, score = 0
1 条评论
-
fsxgc LV 8 @ 2016-11-12 12:02:55
//dijkstra
#include<iostream>
#include<cstdio>
using namespace std;
#include<queue>
#include<vector>
#include<string.h>struct Edge
{
int to;
int dist;
};Edge AddEdge(int to, int dist)
{
Edge e;
e.to = to;
e.dist = dist;
return e;
}
struct HeapNode
{
int u;
int dist;
bool operator < (const HeapNode& h) const
{
return dist > h.dist;
}
};HeapNode NewHN(int u, int dist)
{
HeapNode h;
h.u = u;
h.dist = dist;
return h;
}
const int maxn = 1005;
vector<Edge> G[maxn*maxn/2];
int d[maxn*maxn/2];
bool done[maxn*maxn/2];
int n;void dijkstra(int s)
{
priority_queue<HeapNode> Q;
while (!Q.empty()) Q.pop();
memset(done, false, sizeof(done));
Q.push(NewHN(s,0));while (!Q.empty())
{
HeapNode h = Q.top();
Q.pop();
if (done[h.u]) continue;
done[h.u] = true;
for (int i=0; i<G[h.u].size(); i++)
{
Edge e=G[h.u][i];
if (d[e.to] > e.dist + d[h.u])
{
d[e.to] = e.dist + d[h.u];
Q.push(NewHN(e.to, e.dist));
}
}
}}
int p[maxn][maxn];
int pos(int x, int y)
{
return p[x][y];
}int main()
{
cin>>n;
const int Inf = 1<<30;
for (int i=1; i<=n*(n+1)/2; i++)
d[i] = Inf;
for (int x=1; x<=n; x++)
for (int y=1; y<=n; y++)
p[x][y] = (x-1)*x/2 + y;
int x;
scanf("%d",&x);
G[2].push_back(AddEdge(1, x));
G[3].push_back(AddEdge(1,x));
for (int i=2; i<=n-1; i++)
{
scanf("%d",&x);
Edge e = AddEdge(pos(i, 1), x);
G[pos(i+1,1)].push_back(e);
G[pos(i+1,2)].push_back(e);
G[pos(i+1, i+1)].push_back(e);
G[pos(i, 2)].push_back(e);
G[pos(i, i)].push_back(e);for (int j=2; j<=i-1; j++)
{
scanf("%d",&x);
Edge e = AddEdge(pos(i, j),x);
G[pos(i, j-1)].push_back(e);
G[pos(i, j+1)].push_back(e);
G[pos(i+1, j)].push_back(e);
G[pos(i+1, j+1)].push_back(e);
}
scanf("%d",&x);
e = AddEdge(pos(i, i),x);
G[pos(i+1,1)].push_back(e);
G[pos(i+1,i)].push_back(e);
G[pos(i+1, i+1)].push_back(e);
G[pos(i, 1)].push_back(e);
if (i>2) G[pos(i, i-1)].push_back(e);
}int i=n;
scanf("%d",&x);
d[n*(n-1)/2 + 1] = x;
for (int j=2; j<=i-1; j++)
{
scanf("%d",&x);
Edge e = AddEdge(pos(i, j),x);
G[pos(i, j-1)].push_back(e);
G[pos(i, j+1)].push_back(e);
}
scanf("%d",&x);
Edge e = AddEdge(pos(i, i), x);
G[pos(i, 1)].push_back(e);
if (i>2) G[pos(i, i-1)].push_back(e);dijkstra(n*(n-1)/2 + 1);
cout<<d[1];
return 0;
}
- 1
