375 Zmeu

[•chera_lary]

Salut!
Cum pot optimiza problema aceasta? http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=375
Iau 90 de p, la testul 9 depasesc timpul.
Nu stiu exact unde pierd mai mult timp, ori la Dijkstra ori la permutari.

Cod:

#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#define fin "zmeu.in"
#define fout "zmeu.out"
#define nMax 1001
#define Inf 200001

using namespace std;

int A[nMax][nMax];
int D[6][nMax];
int s[nMax];
int Porti[6];

int n, m, p;
int F[6], FF;
int I[nMax];

void citeste()
{
fstream in(fin, ios::in);
in>>n>>m>>p>>FF;
for(int i=1;i<=5;i++) in>>F[i];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) A[i][j] = 0; else A[i][j] = Inf;
for(int i=1;i<=m;i++)
{
int x, y, c;
in>>x>>y>>c;
A[x][y] = A[y][x] = c;
}
for(int i=1;i<=p;i++)
in>>I[i];
in.close();
}

void Dijkstra(int nod, int f)
{
memset(s, 0, sizeof(s));
s[nod] = 1;

for(int i=1;i<=n;i++)
D[f][i] = A[nod][i];

for(int i=1;i<n;i++)
{
int min = Inf, jmin;
for(int j=1;j<=n;j++)
if(!s[j]) if(min>D[f][j])
{
min = D[f][j];
jmin = j;
}

s[jmin] = 1;
for(int j=1;j<=n;j++)
if(!s[j]) if(D[f][j] > min + A[jmin][j])
D[f][j] = min + A[jmin][j];
}
}

void solve()
{
for(int i=1;i<=5;i++)
Dijkstra(F[i], i);

vector<int> sol;
vector<int>::iterator it;

for(int i=1;i<=5;i++) sol.push_back(i);

for(int i=1;i<=5;i++)
{
int min = Inf;
for(int j=1;j<=p;j++)
if(min > D[i][I[j]]) min = D[i][I[j]];
Porti[i] = min;
}

int Dist = Inf;
do
{
int d;
d = D[sol[0]][FF] + D[sol[1]][F[sol[0]]] + D[sol[2]][F[sol[1]]] + D[sol[3]][F[sol[2]]] + D[sol[4]][F[sol[3]]];
d += Porti[sol[4]];

if(d < Dist) Dist = d;
}while(next_permutation(sol.begin(), sol.end()));

fstream out(fout, ios::out);
out<<Dist<<endl;
out.close();
}

void tipar()
{
for(int i=1;i<=5;i++)
cout<<Porti[i]<<" ";
cout<<endl;
}

int main(void)
{
citeste();
solve();
//tipar();
return 0;
}

[•gabitzish1]

Ai putea incerca sa faci un Dijkstra cu heap'uri ...

[•blasterz]

pai.... de la permutari in niciun caz...

pe campion e compilatorul vechi...schimba citirea

foloseste scanf sau ...parseaza...

@Gabitzish:  nu se merita... e graf dens!!! zice m <= n*(n-1)/2 muchii

LE:sursa ta cu scanf:  http://campion.edu.ro/arhiva/index.php?page=source&action=view&id=26548

[•chera_lary]

ms:P
Nici nu ma asteptam! ) Am mai patit pe anumite probleme, dar acum chiar nu m-am gandit.