LoTrinh.cpp [ LÝ THUYẾT ĐỒ THỊ ]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define vao "LoTrinh.txt"
#define max 1000
#define maxC 10000


FILE *f1, *f2;
long n;
long s, f; // diem xuat phat va ket thuc
char lt[max];
long x;
long a, b; // doan duong bi hu
long c[max][max], Free[max], Trace[max];

void nhap()
{
    f1 = fopen(vao, "r");
    fscanf(f1, "%d", &n);
    fscanf(f1, "%d%d", &s, &f);
    fscanf(f1, "\n");
    fgets(lt, sizeof(lt), f1);
    fscanf(f1, "%d", &x);
    fscanf(f1, "%d%d", &a, &b);
    for (long i = 1; i <= n; i++)
    {
        for (long j = 1; j <= n; j++)
         {      
             fscanf(f1, "%d", &c[i][j]);
        }
    }
       
    fclose(f1);
    //Khoi tao ma tran ke
    for (long i = 1; i <= n; i++)
        for (long j = 1; j <= n; j++)
         {      
            if (i != j && c[i][j] == 0)
                c[i][j] = maxC;
        }
}

long duongdi[max], dodai;
char l[max];
long start;
long d[max];
void xuly()
{
     long m;
     long j = 1;
     m = strlen(lt) - 1;

     int k = 0;
     while(k < m)
     {
         int t = 0;
         while(lt[k] != ' ' && k < m)
         {
             l[t] = lt[k];
             k++;
             t++;
         }
         duongdi[j] = atoi(l);
         j++;
         k++;
     }
     dodai = 0;
     for(int i = 1; i <= n; i++)   
     {
        Trace[i] = -1;
        d[i] = maxC;
        Free[i] = 1;
     }
     for (int i = 1; i < j - 1; i++)
     {
         if (dodai < x)
         {
             dodai += c[duongdi[i]][duongdi[i+1]];
             Trace[duongdi[i+1]] = duongdi[i];
             start = duongdi[i+1];
             Free[duongdi[i]] = 0;
         }
        
     }  
     
     f2 = fopen("DaDi.txt", "w");   
     fprintf(f2, "%d", dodai);   
     fclose(f2);
       
    c[a][b] = maxC;       
}


long dijkstra(long s, long f)
{
   
    d[s] = 0;
   
    do{
        long u = 0;
        long min = maxC;
        for(int i = 1; i <= n; i++)
            if(Free[i] && d[i] < min)
            {
                min = d[i];
                u = i;
            }
           
        if(u==0 || u == f)
            break;
       
        Free[u] = 0;
       
        for(int v = 1; v <= n; v++)
            if(Free[v] && d[v] > d[u] + c[u][v])
            {
                d[v] = d[u] + c[u][v];
                Trace[v] = u;
            }
    }
    while(1);
    return d[f];
}

void xuat()
{
    long kq;
    kq = dijkstra(start,f);
    if(kq == maxC)
    {
        f2 = fopen("ChieuDai.txt", "w");
        fprintf(f2, "0");   
        fclose(f2);   
   
        f2 = fopen("ChiTiet.txt", "w");   
        fprintf(f2, "0");
        fclose(f2);
    }
    else
    {
        kq += dodai;
        f2 = fopen("ChieuDai.txt", "w");
        fprintf(f2, "%d", kq);   
        fclose(f2);   
   
        f2 = fopen("ChiTiet.txt", "w");   
        while(f!=s)
        {
             fprintf(f2,"%d <= ",f);
             f = Trace[f];
        }
        fprintf(f2,"%d\n",s);
        fclose(f2);
    }
}

int main()
{
    nhap();
    xuly();
    xuat();
    return 0;
}