[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Автопат, регионален 2015  XML
Forum Index » Задачи од национални натпревари
Author Message
DushanTerzic



Joined: 09/03/2014 03:17:37
Messages: 2
Offline

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int dist[10010][10010];
int dp[10010];
bool vis[10010];
int t1, t2, n, k;

int Abs(int x)
{
if(x < 0)
return -x;
return x;
}

int solve(int x)
{
queue<int> q;
vis[x] = true;
q.push(x);

while(!q.empty())
{
int curr = q.front(); q.pop();
for(int i = 1; i <= k; i++)
{
if(dist[curr][i] == -1) continue;
if(vis[i]) continue;

q.push(i);
vis[i] = true;
if(i < curr)
{
dp[i] = dp[curr] - dist[curr][i];
}
else
dp[i] = dp[curr] + dist[curr][i];
}
}

return dp[max(t1, t2)];
}

int main() {
memset(dist, -1, sizeof(dist));
cin >> t1 >> t2 >> k >> n;
for(int i = 0; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
dist[b][a] = c;
}

int res = solve(min(t1, t2));
if(res == 0)
cout << -1 << endl;
cout << res << endl;

return 0;
}

Зошто кога го пратам кодот на секој случај ми пишува "Runtime error", но на секој тест пример што го симнам ми вади точен одговор. Да не е проблем до Мендо системот? Ве молам помош.
http://mendo.mk/Task.do?id=537
addictus


[Avatar]

Joined: 08/10/2010 11:22:51
Messages: 23
Location: Куманово
Offline

Dist матрицата која ја користиш зафаќа 382MB меморија, дозволено е само 64MB.

Дадени се највеќе 100,000 познати растојанија. Да кажеме дека сакаш дупло да ги запишуваш (a->b и b->a растојанија во посебни променливи, иако се исти), тоа се 200,000 променливи. Ти за таа намена користиш 100,200,000 променливи. Барај пооптимален начин за запишување на графот.

This message was edited 1 time. Last update was at 09/03/2015 11:23:25


Решенија на задачи - aandevski.wordpress.com
[WWW]
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team