import java.util.Arrays;
public class Graph {
    VNode[] vexs;
    int numOfVexs;
    int maxNumOfVexs;
    boolean[] visited;
    static int[] vertexData;
     int[][] dis1;// 记录最短路径
     int[][] dis2;
     int[][] pre;// 记录前驱顶点
    int[][] jljz;
    int[][] sjjz;
    String[][] name1;
    String[][][] ljname;
	// 初始化
    public  Graph(int maxNumOfVexs){
            this.maxNumOfVexs=maxNumOfVexs;
            vexs=new VNode[maxNumOfVexs];
            numOfVexs=0;
            jljz=new int[maxNumOfVexs][maxNumOfVexs];
            sjjz=new int[maxNumOfVexs][maxNumOfVexs];
            name1=new String[maxNumOfVexs][maxNumOfVexs];
            ljname=new String[maxNumOfVexs][maxNumOfVexs][maxNumOfVexs];
    }
    // 插入一个顶点
    public boolean insertVex(String name,String view){
        if (numOfVexs>=maxNumOfVexs) {
            return false;
        }
        VNode vex=new VNode();
        vex.data=numOfVexs;
        vex.placename=name;
        vex.view=view;
        vexs[numOfVexs++]=vex;
        jljz=new int[numOfVexs][numOfVexs];
        name1=new String[numOfVexs][numOfVexs];
        return true;
    }
    public void showjdxx(){
        for (int i = 0; i < numOfVexs; i++) {
            System.out.println(vexs[i].placename+"的编号为"+i);
        }
    }
    // 插入一条边
    public void insertEdge(int v1,int v2,int value,int time,String name){
        if(value>=0){
            jljz[v1][v2]=value;
            jljz[v2][v1]=value;
        }
        else
           System.out.println("两点距离输出错误");
        if (time>=0) {
            sjjz[v1][v2]=time;
            sjjz[v2][v1]=time;
        }
        else
           System.out.println("两点所需时间错误"); 
        name1[v1][v2]=name;
        name1[v2][v1]=name;
        if (v1<0||v2<0||v1>=numOfVexs||v2>numOfVexs) {
            System.out.println("所查找的两点有误");
        }
        ArcNode vex1=new ArcNode(v2,value,name);
        if (vexs[v1].next==null) {
            vexs[v1].next=vex1;
        }
        else{
            vex1.nextArc=vexs[v1].next;
            vexs[v1].next=vex1;
        }
        ArcNode vex2=new ArcNode(v2,value,name);
        if (vexs[v2].next==null) {
            vexs[v2].next=vex2;
        }
        else{
            vex1.nextArc=vexs[v2].next;
            vexs[v2].next=vex2;
        }
        System.out.println(vexs[v1].placename+"与"+vexs[v2].placename+"两地关系建立成功");
    }
    
// 根据名字删除一个结点
public boolean deleteVex(int data){
    for (int i = 0; i <= numOfVexs; i++) {
        if (vexs[i].data==data) {
            for (int j = i; j < numOfVexs;j++) {
                vexs[j]=vexs[j+1];
            }   
            vexs[numOfVexs]=null;
            numOfVexs--;
            ArcNode current;
            ArcNode previous;
            for (int j = 0; j < numOfVexs; j++) {
                if (vexs[j].next==null) {
                    continue;
                }
                if (vexs[j].next.adjVex==j) {
                    vexs[j].next=null;
                    continue;
                }
                current = vexs[j].next;
                while (current!=null) {
                    previous = current;
                    current =current.nextArc;
                    if (current !=null&&current.adjVex==i) {
                        previous.nextArc=current.nextArc;
                        break;
                    }
                }
            }  
            for (int j = 0; j < numOfVexs; j++) {
                current=vexs[j].next;
                while (current!=null) {
                    if (current.adjVex>i) {
                        current.adjVex--;
                        current=current.nextArc;
                    }
                }
                return true;
            }           
        }
    }
    return false;
}
// 更新地区景点
public void upsetview(String name,String view){
    for (int i = 0; i < numOfVexs; i++) {
        if(vexs[i].placename.equals(name)){
            vexs[i].view=view;
        }
    }
}

// 输出地点的信息
public void showv(String name){
    for (int i = 0; i < numOfVexs; i++) {
        if(vexs[i].placename.equals(name)){
            System.out.println(name+"景区有"+vexs[i].view);
        }
    }
}
// 更新道路信息
public boolean upsetvalue(int v1,int v2,int value,int time,String name){
    // 删边
    ArcNode current = vexs[v1].next;
    ArcNode previous = null;
    while (current != null && current.adjVex != v2) {
        previous = current;
        current = current.nextArc;
    }
    if (current != null)
        previous.nextArc = current.nextArc;
    jljz[v1][v2]=999999;
    // 删除索引为index2的顶点与索引为index1的顶点之间的边
    current = vexs[v2].next;
    while (current != null && current.adjVex != v1) {
        previous = current;
        current = current.nextArc;
    }
    if (current != null)
        previous.adjVex = current.adjVex;
        jljz[v2][v1]=999999;
        // 加边
        jljz[v1][v2]=value;
        sjjz[v1][v2]=time;
        name1[v1][v2]=name;
        jljz[v2][v1]=value;
        sjjz[v2][v1]=time;
        name1[v2][v1]=name;
        if (v1<0||v2<0||v1>=numOfVexs||v2>numOfVexs) {
            return false;
        }
        ArcNode vex1=new ArcNode(v2,value,name);
        if (vexs[v1].next==null) {
            vexs[v1].next=vex1;
        }
        else{
            vex1.nextArc=vexs[v1].next;
            vexs[v1].next=vex1;
        }
        ArcNode vex2=new ArcNode(v2,value,name);
        if (vexs[v2].next==null) {
            vexs[v2].next=vex2;
        }
        else{
            vex1.nextArc=vexs[v2].next;
            vexs[v2].next=vex2;
        }
        
        return true;
   
}
// 删除一条边
public boolean deleteEdge(int v1, int v2) {
    // if (v1 < 0 || v2 < 0 || v1 >= numOfVexs || v2 >= numOfVexs)
    //     throw new ArrayIndexOutOfBoundsException();
    // 删除索引为index1的顶点与索引为index2的顶点之间的边
    ArcNode current = vexs[v1].next;
    ArcNode previous = null;
    while (current != null && current.adjVex != v2) {
        previous = current;
        current = current.nextArc;
    }
    if (current != null)
        previous.nextArc = current.nextArc;
    jljz[v1][v2]=999999;
    // 删除索引为index2的顶点与索引为index1的顶点之间的边
    current = vexs[v2].next;
    while (current != null && current.adjVex != v1) {
        previous = current;
        current = current.nextArc;
    }
    if (current != null)
        previous.adjVex = current.adjVex;
        jljz[v2][v1]=999999;
    return true;
}

// 得到边
public int getEdge(int v1, int v2) {
    // if (v1 < 0 || v2 < 0 || v1 >= numOfVexs || v2 >= numOfVexs)
    //     throw new ArrayIndexOutOfBoundsException();
    ArcNode current = vexs[v1].next;
    while (current != null) {
        if (current.adjVex == v2) {
            return current.value;
        }
        current = current.nextArc;
    }
    
    return 0;
}
// 两点最短路径
    public void Floydjl() {
        vertexData=new int[maxNumOfVexs];
        for (int i = 0; i <= numOfVexs; i++) {
            vertexData[i]=i;
        }
        this.dis1 = jljz;
        for (int i = 0; i < numOfVexs; i++) {
            for (int j = 0; j < dis1.length; j++) {
                if(dis1[i][j]==0&&i!=j){
                    dis1[i][j]=999999;
                }
            }
        }
        this.pre = new int[vertexData.length][vertexData.length];
        for (int i = 0; i < pre.length; i++) {
            Arrays.fill(pre[i], i);
        }
        int len = 0;
            for (int k = 0; k < dis1.length; k++) {
               
                for (int i = 0; i < dis1.length; i++) {
                    for (int j = 0; j < dis1.length; j++) {
                        len = dis1[i][k] + dis1[k][j];
                        if (len < dis1[i][j]) {
                            dis1[i][j] = len;
                            pre[i][j] = pre[k][j];
                          ljname[i][j][k]=vexs[k].placename;                       }
                    }
                }
            }
            for (int i = 0; i <numOfVexs; i++) {
                for (int j = 0; j < numOfVexs; j++) {
                    System.out.println(this.vexs[i].placename + "->" +this.vexs[j].placename + "  的最短路径为:" + this.dis1[i][j]+"km ");
                    System.out.print("路线为");
                    System.out.print(vexs[i].placename+"-->");
                    for (int j2 = 0; j2 < ljname[i][j].length; j2++) {
                        if(ljname[i][j][j2]!=null)
                        System.out.print(ljname[i][j][j2]+"-->");
                    }
                    System.out.print(vexs[j].placename);
                    System.out.println();
                }
                System.out.println();
            }
    }
public void Floydsj() {
    vertexData=new int[maxNumOfVexs];
    for (int i = 0; i <= numOfVexs; i++) {
        vertexData[i]=i;
    }
    this.dis2 = sjjz;
    for (int i = 0; i < numOfVexs; i++) {
        for (int j = 0; j < dis2.length; j++) {
            if(dis2[i][j]==0&&i!=j){
                dis2[i][j]=999999;
            }
        }
    }
    this.pre = new int[vertexData.length][vertexData.length];
    for (int i = 0; i < pre.length; i++) {
        Arrays.fill(pre[i], i);
    }
    int len = 0;
        for (int k = 0; k < dis2.length; k++) {
            for (int i = 0; i < dis2.length; i++) {
                for (int j = 0; j < dis2.length; j++) {
                    len = dis2[i][k] + dis2[k][j];
                    if (len < dis2[i][j]) {
                        dis2[i][j] = len;
                        pre[i][j] = pre[k][j];
                        ljname[i][j][k]=vexs[k].placename;
                    }
                }
            }
        }
        for (int i = 0; i <numOfVexs; i++) {
            for (int j = 0; j < numOfVexs; j++) {
                System.out.println(this.vexs[i].placename + "->" +this.vexs[j].placename + "  的最少时间为:" + this.dis2[i][j]+"h");
                System.out.print("路线为");
                    System.out.print(vexs[i].placename+"-->");
                    for (int j2 = 0; j2 < ljname[i][j].length; j2++) {
                        if(ljname[i][j][j2]!=null)
                        System.out.print(ljname[i][j][j2]+"-->");
                    }
                    System.out.print(vexs[j].placename);
                    System.out.println();
            }
            System.out.println();
        }
    }
    public void shownamejz(){
        for (int i = 0; i < numOfVexs; i++) {
            for (int j = 0; j < numOfVexs; j++) {
                System.out.print(name1[i][j]+"\t");
            }
            System.out.println();
        }
    }
    public void showtimejz(){
        for (int i = 0; i < numOfVexs; i++) {
            for (int j = 0; j < numOfVexs; j++) {
                System.out.print(sjjz[i][j]+"h"+"\t");
            }
            System.out.println();
        }
    }
    public void showjljz(){
        for (int i = 0; i < numOfVexs; i++) {
            for (int j = 0; j < numOfVexs; j++) {
                System.out.print(jljz[i][j]+"km"+"\t");
            }
            System.out.println();
        }
    }
}