Задача с сайта e-olimp № 625.
Ссылка на засчитанное решение.
РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ
Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.
Входные данные
Первая строка входного файла содержит натуральные числа N, M, S и F (N ≤ 5000, M ≤ 100000, 1 ≤ S, F ≤ N, S ≠ F) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.
Следующие M строк содержат по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1 ≤bi, ei ≤ N, 0 ≤ wi ≤ 100000).
Выходные данные
Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F. Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода. Если путь из S в F не существует, выведите -1.
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> #include <vector> #include <set> #include <utility> #include <climits> using namespace std; vector <int> marsh; int main() { int n, m1; cin>>n>>m1; if(n<0 || m1<0){ cout<<"-1"; return 0; } int s,f; cin>>s>>f; if(n==0 || n==1 || s==0 || f==0){ cout<<"-1"<<endl; return 0; } int max; int M[m1][3]; for(int i=0; i<m1 ; i++){ for(int j=0; j<3 ; j++){ cin>>M[i][j]; max=M[0][0]; if(M[i][j]<0){ m1=i; break; } if(M[i][j]<0 ){ cout<<"-1"; return 0; } } } for(int i=0; i<m1 ; i++){ for(int j=0; j<2 ; j++){ if(M[i][j]>max){ max=M[i][j];} } } n=max; int V=n; int h[n]; //массив вершин которые принадлежат минимальному пути от s до f int a[n]; int b[n]; int GR[V][V]; //V for(int i=0; i<n ; i++){ for(int j=0; j<n ; j++){ GR[i][j]=0; } } //преобразовываю считанные данные в матрицу смежности между вершинами for(int i=0; i<m1 ; i++){ for(int j=0; j<3 ; j++){ a[i]=M[i][0]; b[i]=M[i][1]; GR[a[i]-1][b[i]-1]=M[i][2]; GR[b[i]-1][a[i]-1]=M[i][2]; } } int st=s-1; int count, index, i, u, m=st+1; long long distance[V]; bool visited[V]; for (i=0; i<V; i++){ distance[i]=LLONG_MAX; visited[i]=false; } distance[st]=0; long long min; for (count=0; count<V-1; count++){ min=LLONG_MAX; for (i=0; i<V; i++) if (!visited[i] && distance[i]<=min){ min=distance[i]; index=i; } u=index; visited[u]=true; for (i=0; i<V; i++){ //V if (!visited[i] && GR[u][i] && distance[u]!=LLONG_MAX && distance[u]+GR[u][i]<distance[i]){ distance[i]=distance[u]+GR[u][i]; h[i]=u; } } } //вывод расстояния if(n!=0 && n!=1){ for (i=0; i<1; i++){ if(s>n || f>n ){ cout<<"-1"; break; } if(distance[f-1]==LLONG_MAX){ cout<<"-1"<<endl; break; } if (distance[i]!=LLONG_MAX ){ cout<<distance[f-1]<<endl; // вывод маршрута s--; f--; int c=f; while (c!=(s)) { marsh.push_back(c+1); c=h[c]; } marsh.push_back(s+1); cout << marsh[marsh.size()-1]; for(int t = marsh.size()-2; t >=0; t--) cout << " " << marsh[t]; cout << endl; } } } return 0; } |
После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].
неверное решение
Решение успешно проходит тесты на сайте e-olymp. Конечно, вполне возможно, что там слабые тесты.
Если Вы считаете, что решение неверное, то нужно потрудиться и построить тест, который опровергает («ломает») решение. Тогда Вы действительно будете достойны хвалы, что и означает Ваше имя 🙂