#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;
}
Diễn đàn sinh viên công nghệ thông tin, chia sẻ, giao lưu, học hỏi. Kết nối ... Những ngôn ngữ cơ bản mà bạn cần phải nắm nếu muốn thành 1 lập trình viên ...VuaTenMien.Com
Thứ Hai, 16 tháng 3, 2015
LoTrinh.cpp [ LÝ THUYẾT ĐỒ THỊ ]
Đăng ký:
Đăng Nhận xét (Atom)
Bài đăng phổ biến
-
Website-Watcher 2011 sẽ theo dõi và thông báo cho bạn biết mỗi khi trên website, forum, blog,… ưa thích có tin bài mới. Nhờ Website-Watcher...
-
So sánh 2 cách tạo stack bằng mảng và bảng kiểu cấu trúc nhé Mảng: http://codepad.org/rTA0NJgL #include <stdio.h> #include<co...
-
TÀI LIỆU TỔNG HỢP Tài Liệu Đại Học Bách Khoa Hà Nội Tài Liệu Đại Học Bách Khoa Đà Nẵng Tài Liệu Đại Học Bách Khoa HCM Tài Liệu FPT ...
-
NHẬP VÀ XUẤT DỮ LIỆU 4.1 Lệnh xuất Cú pháp : printf ("chuỗi định dạng"[, đối mục 1, đối mục 2,…]); Chức năng : Đưa ...
-
CÂU LỆNH LẶP VỚI SỐ LẦN LẶP CHƯA XÁC ĐỊNH 7.1 Lệnh while Vòng lặp thực hiện lặp lại khối lệnh trong khi biểu thức còn đúng + Cú p...
-
import java.io.*; public class Test_Ngto{ public static void main(String args[]){ InputStream is = System.in; ...
-
BritainTourist .Com PhumyGroup.com SonhaiGroup.com LiaoningGroup .Com S haanxiGroup .com EchinaTourist.com T echnologyJewelry ....
-
//Yêu cầu: Viết chương trình Console Application, tính giai thừa của N nguyên nhập từ bàn phím. GiaiThua=1.2.3.4.....N class Program { ...
-
clear declare -a a a=( [0]=$1 [1]=$2 [2]=$3 ) max=${a[0]} min=${a[0]} l=${#a[*]} for ((i=0;i<$l;i++)) do if [ $max -le ${a[i]} ...
-
using System; namespace PhuongTrinhBacNhat { class Program { static void Main(string[] args) { Console.Write(...
Không có nhận xét nào:
Đăng nhận xét