Go: // Warshall–Floyd Algorithm

package main

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

var scanner = bufio.NewScanner(os.Stdin)

const INF = 2000000000

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
			c_matrix[b-1][a-1] = c
			t_matrix[a-1][b-1] = t
			t_matrix[b-1][a-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
					c_prev[i][j] = -1
				} else {
					c_dist[i][j] = c_matrix[i][j]
					c_prev[i][j] = i
				}
				if t_matrix[i][j] == 0 {
					t_dist[i][j] = INF
					t_prev[i][j] = -1
				} else {
					t_dist[i][j] = t_matrix[i][j]
					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++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int trainTime[101][101];
int trainCost[101][101];

int main(){
	int n,m;
	while(~scanf("%d %d",&n,&m)){
		if(n==m && m==0) break;
		memset(trainTime,0x3,sizeof(trainTime));
		memset(trainCost,0x3,sizeof(trainCost));
		for(int i=0;i<n;i++){
			int a,b,cost,time;
			scanf("%d %d %d %d",&a,&b,&cost,&time);
			trainTime[a][b] = trainTime[b][a] = min(trainTime[a][b],time);
			trainCost[a][b] = trainCost[b][a] = min(trainCost[a][b],cost);
		}

		for(int k=1;k<=m;k++){
			for(int i=1;i<=m;i++){
				for(int j=1;j<=m;j++){
					trainTime[i][j] = min(trainTime[i][k]+trainTime[k][j],trainTime[i][j]);
					trainCost[i][j] = min(trainCost[i][k]+trainCost[k][j],trainCost[i][j]);
				}
			}
		}

		int k;
		scanf("%d",&k);
		for(int i=0;i<k;i++){
			int a,b,r;
			scanf("%d %d %d",&a,&b,&r);
			printf("%d\n", r == 0 ? trainCost[a][b] : trainTime[a][b]);
		}

	}

}

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

#define INF 10000000

// 0: cost , 1 :time
int d[2][101][101];


int main() {
    int n, m, a, b, cost, time, k, p, q, r, i, j;

    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= m; j++) {
            d[0][i][j] = d[1][j][i] = INF;
        }
    }
    for (i = 0; i < n; i++) {
        cin >> a >> b >> cost >> time;
        d[0][a][b] = d[0][b][a] = cost;
        d[1][a][b] = d[1][b][a] = time;
    }

    for (k = 1; k <= m; k++) {
        for (i = 1; i <= m; i++) {
            for (j = 1; j <= m; j++) {
                for (r = 0; r < 2; r++) {
                    if (d[r][i][j] > d[r][i][k] + d[r][k][j]) {
                        d[r][j][i] = d[r][i][j] = d[r][i][k] + d[r][k][j];
                    }
                }
            }
        }
    }

    cin >> k;
    while (k--) {
        cin >> p >> q >> r;
        cout << d[r][p][q] << endl;
    }

    return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)

const int INF = 1<<28, MAXM = 101, COST = 0, TIME = 1;

int cost[2][MAXM][MAXM];
int d[MAXM][MAXM];

int main()
{
    int n, m, a, b, c, t;
    while(cin >> n >> m)
    {
        REP(2)rep(j,m)rep(k,m)cost[i][j][k] = INF;
        //fill(cost, sizeof(cost), INF);
        REP(n)
        {
            cin >> a >> b >> c >> t;
            a--; b--;
            cost[TIME][a][b] = t;
            cost[COST][a][b] = c;
        }

        int k;
        cin >> k;
        int p, q, r;
        rep(s,k)
        {
            cin >> p >> q >> r; p--; q--;

            memset(d, INF , sizeof(d));
            rep(i,m)rep(j,m) d[i][j] = cost[r][i][j];

            rep(l,m)rep(i,m)rep(j,m)
                d[i][j] = min(d[i][j], d[i][l] + d[l][j]);

            cout << d[p][q] << endl;

        }
    }
    return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>

#define INF 1<<30-1

using namespace std;

int n;
int c[101][101];
int t[101][101];
int flg;

int washa(int st,int en,int va){
	if(flg==1){
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(c[i][j]>c[i][k]+c[k][j]){
						c[i][j]=c[i][k]+c[k][j];
					}
					if(t[i][j]>t[i][k]+t[k][j]){
						t[i][j]=t[i][k]+t[k][j];
					}
				}
			}
		}
		flg=0;
	}
	if(va==0){
		return c[st][en];
	}else{
		return t[st][en];
	}
}

int main(){
	int m;
	for(int i=0;i<101;i++){
		for(int j=0;j<101;j++){
			c[i][j]=t[i][j]=INF;
		}
	}
	flg=1;
	
	scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++){
		int a,z,s,x;
		scanf("%d%d%d%d",&a,&z,&s,&x);
		c[a][z]=c[z][a]=s;
		t[a][z]=t[z][a]=x;
	}
	
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int a,z,s;
		scanf("%d%d%d",&a,&z,&s);
		
		printf("%d\n",washa(a,z,s));
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
#define MAX_VAL 200
#define INF 12345678

int V, d[MAX_VAL][MAX_VAL], z[MAX_VAL][MAX_VAL];

void warshall_floyd(int x[MAX_VAL][MAX_VAL]){
	for(int k = 1; k <= V; k++)
		for(int i = 1; i <= V; i++)
			for(int j = 1; j <= V; j++)
				x[i][j] = min(x[i][j],x[i][k]+x[k][j]);
}

int main(){
	int n, k;
	while(true){
		cin>>n>>V;
		
		if(!n&&!V) break;
		
		for(int i = 0; i <= V; i++)
			for(int j = 0; j <= V; j++)d[i][j]=z[i][j] = i == j ? 0 : INF;
		
		for(int i = 1,a,b,cost,time; i <= n; i++){
			cin>>a>>b>>cost>>time;
			d[a][b] = d[b][a] = cost;
			z[a][b] = z[b][a] = time;
		}
		
		warshall_floyd(d);
		warshall_floyd(z);
		
		cin>>k;
		
		for(int i = 1,p,q,r; i <= k; i++){
			cin>>p>>q>>r;
			if(r)cout<<z[p][q]<<endl;
			else cout<<d[p][q]<<endl;
		}
	}
	
	return 0;
}