Time limit: 5000ms
Memory limit: 256mb

Description (Optional):
Similar to exercise 3, there is an undirected graph. You need to store all edge weights in a two-dimensional array cost[][] and calculate all pairs shortest distance. Suppose there are at most 100 nodes. If there is no edge between two nodes, we set their weight to a very large number, MAX_DIS=999999, to denote these two nodes are not connected directly.


In this exercise, you are required to fulfill the following three tasks.

1. Initialize Cost Array
Same to ex1, initially, we have the array cost[100][100] to store the edge cost. We input the total nodes number n and edges number m, and then input all edges with  format, where w is the weight of edge (x,y). If there is no edge between two nodes, we set the cost to be MAX_DIS.

2. Calculate All Pairs Shortest Distance and Store Shortest Path
With the cost array, we need to compute the shortest distance between every two nodes and store the corresponding shortest path. Also, we need to initialize the distance array distance[100][100] and the path array path[100][100] at first. The element path[x][y] records the first node in the path from node x to node y. Then in each loop for (x,y), we find whether there is another path's distance less than distance[x][y]. If there is, we update the distance[x][y] and path[x][y]. For more detail, you can refer to lecture notes.

3. Output Shortest Path and Shortest Distance
We need to print the shortest path from any input source node x to destination node y, and its corresponding distance.

The main function has been provided. It first asks the user to input the total nodes number n and edges number m, input all these edges to initialize the cost array, and the source node x and destination node y that are used to output the shortest distance. Then it invokes the function floyd to calculate all pairs shortest distance. And last we output the the shortest path and shortest distance from node x to node y. 

You need to complete three functions.


void initial();

void floyd();

void print_path();


Sample Input 1:
3 3
0 1 2
1 2 3
0 2 4
1 2

Sample Output 1:
Input the number of nodes:
Input the number of edges:
Input these edges:
Input source node and destination node:
1->2=3


Sample Input 2:
2 0
0 1

Sample Output 2:
Input the number of nodes:
Input the number of edges:
Input these edges:
Input source node and destination node:
0->1=999999


Sample Input 3:
5 8
0 1 3
1 3 4
3 2 8 
2 5 4
0 3 2
1 4 10
5 4 2
3 5 8
2 4

Sample Output 3:
Input the number of nodes:
Input the number of edges:
Input these edges:
Input source node and destination node:
2->3->1->4=22


Sample Input 4:
8 10
0 1 2
1 2 9
2 3 4
3 5 7
2 4 8
5 6 10
6 7 8
7 5 1
7 3 4
0 4 10

Sample Output 4:
Input the number of nodes:
Input the number of edges:
Input these edges:
Input source node and destination node:
0->1->2->3->7->6=27

Code Template:

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

#include 
#include 

#define MAX_NODES 100
#define MAX_DIS 999999


int cost[MAX_NODES][MAX_NODES];
int distance[MAX_NODES][MAX_NODES];
int path[MAX_NODES][MAX_NODES];

void initial(int m, int n);

void floyd(int n);

void print_path(int x, int y);

void initial(int m, int n)
{
    /*
	initialize cost[][].
	note that if no edge between (x,y), set cost[x][y]=MAX_DIS
	     and cost[a][b]=cost[b][a] for the undirected graph. 
        Fill in your code here...
    */
}

void floyd(int n)
{
    /*
        Fill in your code here...
        calculate all pairs shortest paths.
    */
}

void print_path(int x, int y)
{
        /*
        Fill in your code here...
        print the shortest path and shortest distance from node x to node y.
    */
}

int main()
{
    int m,n,x,y;
    printf("Input the number of nodes:\n");
    scanf("%d",&n);
    printf("Input the number of edges:\n");
    scanf("%d",&m);
    printf("Input these edges:\n");
    initial(m,n);
    floyd(n);
    printf("Input source node and destination node:\n");
    scanf("%d%d",&x,&y);
    print_path(x,y);
    return 0;
}