---
# System prepended metadata

title: '*2022/05/17 演算法作業 HW04*'
tags: [演算法]

---

###### tags: `演算法`
# *2022/05/17 演算法作業 HW04*
## 題目
![](https://i.imgur.com/4JZ1u9j.png)
## 繪圖
![](https://i.imgur.com/idRXn8S.png)

## 土法煉鋼:
![](https://i.imgur.com/YxnIZMG.png)
![](https://i.imgur.com/bdDgRXP.png)
![](https://i.imgur.com/lS8BDAT.png)
![](https://i.imgur.com/0itBemy.png)
![](https://i.imgur.com/NQoFWsa.png)


## 文明方法-程式

```
#include<iostream>
using namespace std;

int ary[10][10], completed[10], n, cost = 0;
void takeInput(){
	int i, j;
	cout << "Enter the number of node: ";
	cin >> n;
	cout << "\nEnter the Weight Matrix\n";
	for (i = 0; i < n; i++){
		cout << "\nEnter Elements of Row: " << i + 1 << "\n";
		for (j = 0; j < n; j++) {
			cin >> ary[i][j];
		}
		completed[i] = 0;
	}
	cout << "\n\nThe weight list is:";
	for (i = 0; i < n; i++){
		cout << "\n";
		for (j = 0; j < n; j++) {
			cout << "\t" << ary[i][j];
		}
	}
}


int least(int c){
	int i, nc = 999;
	int min = 999, kmin;
	for (i = 0; i < n; i++){
		if ((ary[c][i] != 0) && (completed[i] == 0)) {
			if (ary[c][i] + ary[i][c] < min){
				min = ary[i][0] + ary[c][i];
				kmin = ary[c][i];
				nc = i;
			}
		}
	}
	if (min != 999) {
		cost += kmin;
	}
	return nc;
}
void mincost(int city){
	int i, ncity;
	completed[city] = 1;
	cout << city + 1 << "--->";
	ncity = least(city);
	if (ncity == 999){
		ncity = 0;
		cout << ncity + 1;
		cost += ary[city][ncity];
		return;
	}
	mincost(ncity);
}
int main(){
	takeInput();
	cout << "\n\nThe Path is:\n";
	mincost(0); //passing 0 because starting vertex
	cout << "\n\nMinimum cost is " << cost;
	return 0;
}

```
Reference From : https://reurl.cc/OAMjyv

## 所得結果
V1->V2->V3->V5->V4->V1
cost: 29
