Здравствуйте!!! В очередной раз прошу вас о помощи. Пожалуйста, помогите решить данную задачу. Ссылка здесь. Попробовал решить её, но десятый тест не проходит. Может в коде есть ошибка? Вот код:
#include <bits/stdc++.h>
using namespace std;
const int INF=1000000;
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n,m,i,j,x,a,b;
cin >> n;
vector<int> w[n],d;
vector<bool> u;
for(i=0;i<n;i++){
cin >> x;
for(j=0;j<n;j++) w[i].push_back(x);
u.push_back(false);
d.push_back(INF);
}
cin >> m;
vector<int> g[n];
for(i=0;i<m;i++){
cin >> a >> b;
g[a-1].push_back(b-1);
g[b-1].push_back(a-1);
}
int bak=INF,s=0,e=n-1;
d[s]=0;
for(i=0;i<n;i++){
int v=-1;
for(j=0;j<n;j++)
if(!u[j] && (v==-1 || d[j]<d[v])) v=j;
if(d[v]==INF) break;
u[v]=true;
int ln=g[v].size();
for(size_t j=0;j<ln;j++){
int to=g[v][j],min1=d[v]+w[v][0],min2=d[v]+bak;
if(min1<=min2 && min1<d[to]){
d[to] = min1;
bak = min(bak,w[v][0]);
}
else if(min2<min1 && min2<d[to]){
d[to] = min2;
bak = w[v][0];
}
else{
bak = min(bak,w[v][0]);
}
}
}
if(d[e]==INF) cout << -1;
else cout << d[e];
return 0;
}
Для этой задачи нужно хранить d[N][3], d[i][j] — минимальные затраты, чтобы приехать в город i с j баками бензина. Переходы будут такие: из состояния (i, j) в (i, j + 1), если мы покупаем бензин в этом городе (j < 2) и из (i, j) в (u, j — 1) если мы едем в соседний город (j > 0).
Спасибо большое за решение!