Matematyka.pl

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
}