using?System;
using?System.Collections.Generic;
using?System.Text;

namespace?play
{
????class?Vertex
????{
????????public?Vertex（string?vna）
????????{
????????????vname?=?vna;
????????????wasVisited?=?false;
????????}
????????public?string?vname;
????????public?bool?wasVisited;
????}

????class?Graph
????{
????????private?Vertex[]?vertices?=?new?Vertex[10];
????????private?int[]?cost?=?new?int[10?10];//鄰近矩陣包含邊的代價
????????private?int?n;//n是頂點的數目
????????int?infinity?=?9999999;//將非常大的值作為無窮大。
????????Stack?thestack?=?new?Stack（10）;
????????Queue?thequeue?=?new?Queue（）;

????????public?Graph（）
????????{
????????????n?=?0;
????????????for?（int?i?=?0;?i?????????????????for?（int?j?=?0;?j?????????????????{
????????????????????if?（i?==?j）
????????????????????????cost[i?j]?=?0;
????????????????????else
????????????????????????cost[i?j]?=?infinity;
????????????????}
????????}

????????private?bool?edgeExists（）
????????{
????????????for?（int?i?=?0;?i?????????????????for?（int?j?=?0;?j?????????????????????if?（（cost[i?j]?!=?0）?&&?（cost[i?j]?!=?infinity））
????????????????????????return?（true）;
????????????return?（false）;
????????}

????????public?void?addVertex（string?vnam）
????????{
????????????int?i?=?getIndex（vnam）;
????????????if?（i?!=?-1）
????????????{
????????????????Console.WriteLine（“\n該景點已經存在。“）;
????????????????return;
????????????}
????????????vertices[n]?=?new?Vertex（vnam）;
????????????n++;
????????}

????????private?int?getIndex（string?vname）
????????{
????????????for?（int?i?=?0;?i?????????????????if?（vertices[i].vname?==?vname）
????????????????????return?（i）;
????????????return?（-1）;//如果在列表中沒有找到，返回-1。
????????}

????????public?void?addEdge（string?v1?string?v2?int?a）
????????{
????????????int?i1?i2;
????????????if?（n?==?0）
????????????{
????????????????Console.WriteLine（“\n不存在任何景點。你需要先增加一個景點。“）;
????????????????return;
????????????}
????????????while?（true）
????????????{
????????????????i1?=?getIndex（v1）;
????????????????if?（i1?==?-1）
????????????????????Console.WriteLine（“\n該起始景點不存在，請重試。“）;
????????????????else
????????????????????break;
????????????}
????????????while?（true）
????????????{
????????????????i2?=?getIndex（v2）;
????????????????if?（i2?==?-1）
????????????????????Console.WriteLine（“\n該目的地景點不存在，請重試。“）;
????????????????else
????????????????????break;
????????????}
????????????cost[i1?i2]?=?cost[i2?i1]?=?a;
????????}

????????public?void?display（）
????????{
????????????if?（n?==?0）
????????????{
????????????????Console.WriteLine（“\n圖不存在。“）;
????????????????return;
????????????}
????????????Console.WriteLine（“\n景點：“）;
????????????for?（int?i?=?0;?i?????????????????Console.WriteLine（vertices[i].vname）;

????????????if?（edgeExists（））
????????????{
????????????????Console.WriteLine（“\n路徑：“）;
????????????????for?（int?i?=?0;?i?