Go: // Warshall–Floyd Algorithm

package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

const INF = 0x7FFFFFFF

func main() {
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		n, _ := strconv.Atoi(buf[0])
		m, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		c_matrix := make([][]int, m)
		for i := range c_matrix {
			c_matrix[i] = make([]int, m)
		}
		t_matrix := make([][]int, m)
		for i := range t_matrix {
			t_matrix[i] = make([]int, m)
		}
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			a, _ := strconv.Atoi(buf_[0])
			b, _ := strconv.Atoi(buf_[1])
			c, _ := strconv.Atoi(buf_[2])
			t, _ := strconv.Atoi(buf_[3])
			c_matrix[a-1][b-1] = c
			t_matrix[a-1][b-1] = t
		}
		c_dist := make([][]int, m)
		c_prev := make([][]int, m)
		t_dist := make([][]int, m)
		t_prev := make([][]int, m)
		for i := 0; i < m; i++ {
			c_dist[i] = make([]int, m)
			c_prev[i] = make([]int, m)
			t_dist[i] = make([]int, m)
			t_prev[i] = make([]int, m)
		}
		for i := 0; i < m; i++ {
			for j := 0; j < m; j++ {
				if c_matrix[i][j] == 0{
					c_dist[i][j] = INF
				} else {
					c_dist[i][j] = c_matrix[i][j]
				}
				if c_matrix[i][j] == 0{
					c_prev[i][j] = -1
				} else {
					c_prev[i][j] = i
				}
				if t_matrix[i][j] == 0{
					t_dist[i][j] = INF
				} else {
					t_dist[i][j] = t_matrix[i][j]
				}
				if t_matrix[i][j] == 0{
					t_prev[i][j] = -1
				} else {
					t_prev[i][j] = i
				}
			}
			c_dist[i][i] = 0
			t_dist[i][i] = 0
		}
		for k := 0; k < m; k++ {
			for i := 0; i < m; i++ {
				for j := 0; j < m; j++ {
					c_newlen := c_dist[i][k] + c_dist[k][j]
					if c_newlen < c_dist[i][j] {
						c_dist[i][j] = c_newlen
						c_prev[i][j] = c_prev[k][j]
					}
				}
			}
		}
		for k := 0; k < m; k++ {
			for i := 0; i < m; i++ {
				for j := 0; j < m; j++ {
					t_newlen := t_dist[i][k] + t_dist[k][j]
					if t_newlen < t_dist[i][j] {
						t_dist[i][j] = t_newlen
						t_prev[i][j] = t_prev[k][j]
					}

				}
			}
		}
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())
		for i := 0; i < k; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			p, _ := strconv.Atoi(buf_[0])
			q, _ := strconv.Atoi(buf_[1])
			r, _ := strconv.Atoi(buf_[2])
			switch r {
			case 0: fmt.Println(c_dist[p-1][q-1])
			case 1: fmt.Println(t_dist[p-1][q-1])
			}
		}
	}
}

C++: #include <stdio.h>
#include <limits.h>

const int INF = INT_MAX;

int main(void)
{
	int n, m, a, b, k, t;
	int tcost[105][105], mcost[105][105], node[105], used[105];
	int i, j, min, cost, time;
	
	while (1){
		scanf("%d %d", &n, &m);
		
		if (n == 0 && m == 0){
			break;
		}
		
		for (i = 0; i < m; i++){
			for (j = 0; j < m; j++){
				mcost[i][j] = INF;
				tcost[i][j] = INF;
			}
		}
		
		for (i = 0; i < n; i++){
			scanf("%d %d", &a, &b);
			a--; b--;
			scanf("%d %d", &cost, &time);
			
			if (cost < mcost[a][b]){
				mcost[a][b] = cost;
				mcost[b][a] = cost;
			}
			if (time < tcost[a][b]){
				tcost[a][b] = time;
				tcost[b][a] = time;
			}
			
		}
		
		scanf("%d", &k);
		
		for (i = 0; i < k; i++){
			scanf("%d %d %d", &a, &b, &t);
			a--; b--;
			for (j = 0; j < m; j++){
				node[j] = INF;
				used[j] = 0;
			}
			
			node[a] = 0;
			while (1){
				used[a] = 1;
				min = INF;
				
				for (j = 0; j < m; j++){
					if (t == 1){
						if (used[j] == 0 && tcost[a][j] != INF && node[j] > node[a] + tcost[a][j]){
							node[j] = node[a] + tcost[a][j];
						}
						if (used[j] == 0 && min > node[j]){
							min = j;
						}
					}
					else{
						if (used[j] == 0 && mcost[a][j] != INF && node[j] > node[a] + mcost[a][j]){
							node[j] = node[a] + mcost[a][j];
						}
						if (used[j] == 0 && min > node[j]){
							min = j;
						}
					}
				}
				a = min;
				if (a == b){
					break;
				}
			}
			printf("%d\n", node[b]);
		}
	}
	return (0);
}

C++: #include<iostream>
#include<vector>

using namespace std;

int data_cost[101][101],data_time[101][101],prev_cost[101][101],prev_time[101][101],total_cost[101][101],total_time[101][101];
vector<int> array[101];

void serch(int st,int now)
{
	int i,flag=0;
	for(i=0;i<array[now].size();i++)
	{
		if(prev_cost[now][array[now][i]]==1)
			flag++;
	}
	if(flag==array[now].size())
	{
		return ;
	}
	else
	{
		total_cost[st][st]=0;
		total_time[st][st]=0;
		for(i=0;i<array[now].size();i++)
		{
			if(prev_cost[now][array[now][i]]!=1)
			{
				if(total_cost[st][array[now][i]]>total_cost[st][now]+data_cost[now][array[now][i]])
				{
					total_cost[st][array[now][i]]=total_cost[st][now]+data_cost[now][array[now][i]];
				}
				if(total_time[st][array[now][i]]>total_time[st][now]+data_time[array[now][i]][now])
				{
					total_time[st][array[now][i]]=total_time[st][now]+data_time[array[now][i]][now];
				}
			}
			prev_cost[now][array[now][i]]=prev_cost[array[now][i]][now]=1;
		}
		for(int j=0;j<array[now].size();j++)
		{
			serch(st,array[now][j]);
		}
	}
	return ;
}


int main()
{
	
	int n,m,i,j;
	
	for(;;)
	{
		cin >> n >> m ;
		if(n==0 && m==0)
			break;
		
		
		for(i=0;i<101;i++)
		{
			array[i].clear();
		}
		
		for(i=0;i<n;i++)
		{
			int a,b,cost,time;
			cin >> a >> b >> cost >> time ;
			array[a].push_back(b);
			array[b].push_back(a);
			data_cost[a][b]=cost;
			data_time[a][b]=time;
			data_cost[b][a]=cost;
			data_time[b][a]=time;
		}
		
		for(i=1;i<m+1;i++)
		{
			for(j=1;j<m+1;j++)
			{
				total_cost[i][j]=1000000;
				total_time[i][j]=1000000;
				for(int k=1;k<m+1;k++)
				{
					prev_cost[j][k]=0;
					prev_time[j][k]=0;
				}
			}
			serch(i,i);
		}
		int  num;
		cin >> num ;
		
		for(int k=0;k<num;k++)
		{
			int st,en,se;
			cin >> st >> en >> se ;
			
			if(se==0)
				cout << total_cost[st][en] << endl;
			else
				cout << total_time[st][en] << endl;
		}
	}
}

C++: #include<iostream>
#include<map>
#include<set>
#include<queue>
using namespace std;

#define P pair<int, int>
#define MAX_M 300
#define MAX_N 100

int n, m, k, trainMap[MAX_N + 1][MAX_N + 1][2];

void resetTrainMap();
void inputTrainMap(int n);
int check(int p, int q, int r);

int main(){
    while(cin >>n >>m){
        if(n == 0 && m == 0) break;
        resetTrainMap();
        inputTrainMap(n);
        cin >>k;
        for(int i = 0; i < k; i++){
            int p, q, r;
            cin >>p >>q >>r;
            cout <<check(p, q, r) <<endl;
        }
    }
    return 0;
}

void resetTrainMap(){
    for(int i = 0; i <= MAX_N; i++){
        for(int j = 0; j <= MAX_N; j++){
            trainMap[i][j][0] = -1;
            trainMap[i][j][1] = -1;
        }
    }
}

void inputTrainMap(int n){
    for(int i = 0; i < n; i++){
        int a, b, c, t;
        cin >>a >>b >>c >>t;
        trainMap[a][b][0] = c;
        trainMap[b][a][0] = c;
        trainMap[a][b][1] = t;
        trainMap[b][a][1] = t;
    }
}

int check(int p, int q, int r){
    queue<P> ansQu; //f = cost or time
    map<int, int> ansMap;
    for(int i = 1; i <= m; i++) ansMap.insert( map<int, int>::value_type(i, -1) );
    ansQu.push( make_pair(p, 0) );
    while(!ansQu.empty()){
        P nowq = ansQu.front();
        for(int i = 1; i <= m; i++){
            if(trainMap[nowq.first][i][r] != -1){
                if(nowq.second + trainMap[nowq.first][i][r] < ansMap[i] || ansMap[i] == -1){
                    ansMap[i] = nowq.second + trainMap[nowq.first][i][r];
                    ansQu.push( make_pair(i, ansMap[i]) );
                }
            }
        }
        ansQu.pop();
    }
    return ansMap[q];
}