io sottopongo il problema e mi da dei casi sbagliati che in locale sono giusti(come il terzo esempio)mi sapreste dire il perchè?
Grazie in anticipo vi lascio il codice di seguito:
#include<bits/stdc++.h>
using namespace std;
vector<long long> altezze(100001);
vector<int> a(100001), b(100001), c(100001);
vector<vector<pair<long long int,long long int> > >vinco(100001);
void cambia(long long int i){
long long int cont=0;
while(cont<vinco[i].size()){
if(altezze[vinco[i][cont].first]>altezze[i]+vinco[i][cont].second){
altezze[vinco[i][cont].first]=altezze[i]+vinco[i][cont].second;
cambia(vinco[i][cont].first);
}
cont++;
}
}
long long int costruisci(int N, int M, vector<long long>& altezze, vector<int>& a, vector<int>& b, vector<int>& c){
for(long long int i=0;i<M;i++){
pair<long long int,long long int>coppia;
coppia.first=b[i];
coppia.second=c[i];
vinco[a[i]].push_back(coppia);
}
for(long long int I=0;I<N;I++){
for(long long int J=0;J<vinco[I].size();J++){
if(altezze[vinco[I][J].first]>altezze[I]+vinco[I][J].second){
altezze[vinco[I][J].first]=altezze[I]+vinco[I][J].second;
cambia(vinco[I][J].first);
}
}
}
long long int som=0;
for(long long int i=0;i<N;i++){
som+=altezze[i];
}
return som;
}
//in sottoposizione ho messo solo il codice prima di questo commento
//quello dopo è solo per provare se funziona
int main(){
long long int N,M;
cin>>N>>M;
for(long long int i=0;i<N;i++){
cin>>altezze[i];
}
for(long long int i=0;i<M;i++){
cin>>a[i]>>b[i]>>c[i];
}
cout<<costruisci(N,M,altezze,a,b,c);
}