old_task_S(wrong)

#include <stdio.h>
#include <limits.h>

#define MAX_LENGTH_ARC 501501
#define MAX_COUNTR_VERTEX 1003

typedef struct e{
    int len;
    int towns;
}e;

e map[501501];
int last[MAX_COUNTR_VERTEX];
int used[MAX_COUNTR_VERTEX];
int P[MAX_COUNTR_VERTEX];

//make "index" from v
int makeIndex(int vert1, int vert2) {
    if (vert1 > vert2) {
        return (vert1 * (vert1 - 1)) / 2 + vert2;
    } else {
        return (vert2 * (vert2 - 1)) / 2 + vert1;
    }
}
void djkstr(int s, int N, int Finish, FILE *output){
    //int k = 0;
    int dist[MAX_COUNTR_VERTEX];

    for(int i = 0; i < MAX_COUNTR_VERTEX; i++){
        dist[i] = INT_MAX;
        used[i] = 0;
        last[i] = 0;
    }
    dist[s] = 0;

    for(int i = 0; i < MAX_COUNTR_VERTEX; i++){
        int v = -1;
        for(int j = 0; j < MAX_COUNTR_VERTEX; j++){
            if (!used[j] && dist[j] < dist[v]){
                v = j;
            }
        }
        if(dist[v] == INT_MAX){
            break;
        }

        used[v] = 1;

        for(int y = 0; y < N; y++){
            int index = makeIndex(v, y);//index (N + 1)*N/2 - (1 + (N - s))*(N - s)/2 + (N - s) - (N - y);
            if(map[index].len != INT_MIN) {//если есть путь, то проводим релаксацию

                int len = map[index].len + P[y];//стоимость перехода +пошлина

                if (dist[v] + len <= dist[y]) {
                    if(dist[v] + len == dist[y]) {
                        if(map[y].towns <= (map[v].towns + 1)){
                            last[y] = v;
                            map[y].towns = map[v].towns + 1;
                        }
                    }
                    else{
                        dist[y] = dist[v] + len;
                        last[y] = v;
                        map[y].towns = map[v].towns + 1;
                    }
                }
            }
        }
    }
    int count;
    int buff = Finish;
    while(buff != s){
        fprintf(output,"%d\n", last[buff]);
        buff = last[buff];
    }
    fprintf(output,"%d", s);

}

int main() {
    //бфс с очередями с приоритетами
    for(int i = 0; i < 501000; i++){
        map[i].len = -1;
        map[i].towns = -1;
    }

    FILE * input = fopen("input.txt","r");
    FILE * output = fopen("output.txt","w");

    int N = 0;
    fscanf(input,"%d\n", &N);
    for(int i = 0; i < N; i++) {
        fscanf(input, "%d",&P[i]);
    }
    fscanf(input,"\n");
    fscanf(input," \n");

    int M = 0;
    int index = 0;
    fscanf(input,"%d",&M);
    for(int i = 0; i < M; i++){
        int x, y, w;
        fscanf(input, "%d %d %d\n", &x, &y, &w);
        if(y > x){
            x = x + y;//swap
            y = x - y;
            x = x - y;
        }
        index = makeIndex(x, y);

        //Map[(N + 1)*N/2 - (1 + (N - x))*(N - x)/2 + (N - x) - (N - y)].len = w;//Map[x][y] = w;//(N + 1)*N/2 - (1 + (N - x))*(N - x)/2 + (N - x) - (N - y);
        //Map[(N + 1)*N/2 - (1 + (N - x))*(N - x)/2 + (N - x) - (N - y)].to = y;
        map[index].len = w;
    }
    fscanf(input, "\n");

    int Start, Finish;
    fscanf(input, "%d %d", &Start, &Finish);

    djkstr(Start, N, Finish, output);

    //for(int y = 0; y < 1001; y++){
    //    for(int x = y + 1; x < 1001; x++){
  //          if(Map[x][y] != NULL){
//
        //    }
      //  }
    //}
    //(n+1)*n/2 - (1+(n-l))*(n-l)/2 + (n-l)-(n-r)
    //для 3,4 : 15 - 3 + 2 - 1 = 13;
    //n - кол-во вершин
    //l, r - ака координаты
    //если л > r нужно поменять местами
    fclose(input);
    fclose(output);
    return 0;
}