rozwiazanie:
Kod: Zaznacz cały
//---------------------------------------------------------------------------
#include<iostream>
#include<vector>
using namespace std;
//---------------------------------------------------------------------------
/*
Algorytm Dijksty
Adj-listy sasiedztwa
w-wagi krawedzi
u-zrodlo
0,1,...,n-1-wierzcholki
d-odleglosc od zrodla
*/
//---------------------------------------------------------------------------
void Dijkstra( vector< vector<int> > &Adj, vector< vector<int> > &w, vector<long long> &d, int u);
//---------------------------------------------------------------------------
int main()
{
ios_base::sync_with_stdio(0);
int n, m;
cin>>n;
vector<int> p(n);
for(int i(0); i<n; ++i)
cin>>p[i];
int a,b,c;
vector< vector<int> > Adj(n);
vector< vector<int> > w(n);
vector<long long> d_from_s(n);
vector< vector<int> > TAdj(n); //transpozycja
vector<long long> d_to_s(n);
vector< vector<int> > Tw(n);
cin>>m;
for(int i(0); i<m; ++i)
{
cin>>a>>b>>c;
Adj[a-1].push_back(b-1);
w[a-1].push_back(c);
TAdj[b-1].push_back(a-1);
Tw[b-1].push_back(c);
}
Dijkstra(Adj, w, d_from_s, 0);
Dijkstra(TAdj, Tw, d_to_s, 0);
long minimum = 0.5*p[0];
for(int i(1); i<n; ++i)
{
if(d_from_s[i]!=-1 && d_to_s[i]!=-1 && d_from_s[i]+0.5*p[i]+d_to_s[i]<minimum)
minimum=d_from_s[i]+0.5*p[i]+d_to_s[i];
}
cout<<minimum<<endl;
return(0);
}
//---------------------------------------------------------------------------
//zlozonosc obliczeniowa: O(V^2)
void Dijkstra( vector< vector<int> > &Adj, vector< vector<int> > &w, vector<long long> &d, int u)
{
int n(Adj.size());
vector<long long> Q;
for(int i(0); i<n; ++i)
{
d[i]=-1;
Q.push_back(i);
}
d[u]=0; //sciema
int min;
int counter;
while(!Q.empty())
{
//znajdowanie najblizszego nieusunietego wierzcholka
counter=0;
for(int i(1); i<Q.size(); ++i)
if(d[Q[i]]!=-1 && d[Q[i]]<d[Q[counter]])
counter=i;
if(d[counter]==-1)
{
d[u]=-1;
return;
}
min=Q[counter];
Q.erase(Q.begin()+counter);
//ciag relakcacji
for(int i(0); i<Adj[min].size(); ++i)
if(d[Adj[min][i]]==-1 ||(d[Adj[min][i]]>d[min]+w[min][i]))
d[Adj[min][i]]=d[min]+w[min][i];
}
d[u]=-1; //naprawa sciemy
}
Ukryta treść:
2x algorytm Dijkstry - dla grafu i dla jego transpozycji za kazdym razem zrodlem jest wierzcholek 0 (złoto). mam obliczone odleglosci miedzy wierzcholkiem 0 a kazdym innym i na odwrot, wiec liniowo moge wyznaczyc minimum. blad tkwi raczej w kodzie bo poprawnosc rozumowana jest raczej oczywista