a

b

c

d

e

0 1 4

0 2 2

1 2 3

1 3 2

1 4 3

2 1 1

2 3 4

2 4 5

4 3 1

#include <iostream>

#include <string>

using namespace std;  

const int maxVertexNum = 20;

const int INF = 99999;

typedef struct dGraph{

	// vertexes

	string vertex[maxVertexNum];

	// edges

	int edges[maxVertexNum][maxVertexNum];

	int vertexNum;

	int edgeNum;

	// construct a graph

	void set(int n, int e) {

		vertexNum = n;

		edgeNum = e;

		//cout << "input vertex" << endl;

		for (int i = 0; i < n; i++)

	        cin >> vertex[i];

	    for (int i = 0; i < n; i++)

		    for (int j = 0; j < n ; j++)

		        edges[i][j] = INF;

		//cout << "input edge" << endl;

	    int weight;

	    for (int m = 0; m < e; m++) {

	    	int i,j;

	    	cin >> i >> j >> weight;

			edges[i][j] = weight;

		}

	}

	// Dijkstra's shortest-path alogorithm

	void shortestPathDj(int v) {

		bool visited[vertexNum] = {false};

		int dist[vertexNum] = {INF};

		string path[2 * vertexNum];

		// initiation

		for (int i = 0; i < vertexNum; i++) {

			dist[i] = edges[v][i];

			if (dist[i] < INF)

			    path[i] = vertex[v]+vertex[i];

			else

			    path[i] = "";

		}

		dist[v] = 0;

		visited[v] = 1;

		//

		int min;

		int i, j, k;

		for (j = 1; j < vertexNum; j++) {

			min = INF;

			// find shortest edge.

			for (i = 0; i < vertexNum; i++) {

				if (dist[i] < min && visited[i] == false) {

					min = dist[i];

					k = i;

				}

			}

			visited[k] = true;

			cout<<path[k]<<" "<<dist[k]<<endl;

			for (i = 0; i < vertexNum; i++) {

				if (dist[i] > dist[k] + edges[k][i] && visited[i] == false) {

					dist[i] = dist[k] + edges[k][i];

					path[i] = path[k] + vertex[i];

				}

			}

		}

	}

} dGraph;

int main() {

	freopen("in.txt", "r", stdin);

	dGraph G;

	G.set(5,9);

	G.shortestPathDj(0);

	return 0;

}