Ответ одного теста влияет на следующий в алгоритме Dijsktra - PullRequest
Новая
       65

Ответ одного теста влияет на следующий в алгоритме Dijsktra

0 голосов
/ 15 апреля 2020

Я пытаюсь найти кратчайшее расстояние для Т-тестов. Мой код успешно выполняется для первого теста, но он добавляет результат предыдущего теста в следующий тест. Я не уверен, почему это происходит. Что мне нужно сделать, чтобы сделать ответ полностью независимым от предыдущего теста? 

#include<bits/stdc++.h>
const int INF = 1e18;
using namespace std;
vector<pair<int, int>> adj[300005];
void dijkstra(int s,int n, int t) 
{
    int b=1;
    vector<int> d;
    vector<int> p;
    d.assign(n, INF);// distance
    p.assign(n, -1);// parent
    vector<bool> u(n, false);// visited array

    d[s] = 0;// distance(source=0)
    for (int i = 0; i < n; i++) 
    {
        int v = -1;
        for (int j = 0; j < n; j++) 
        {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;//Min Distance vala vertex
        }


        u[v] = true;
        for (auto edge : adj[v]) 
        {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) 
            {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
    if(d[t]!=INF)
    {
        cout<<d[t]<<endl;
    }
    else
        cout<<"-1"<<endl;
}
 signed main() 
{ 
    FAST;
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        rep(i,0,m)
        {
            int a,b,w;
            cin>>a>>b>>w;
            a--;b--;
            adj[a].push_back(make_pair(b,w));
        }
        int x,y;
        cin>>x>>y;
        x--;y--;


        dijkstra(x,n,y);
    }
    return 0; 
}
...