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 <iostream>
#include <algorithm>
#include <utility>
 
using namespace std;
 
int kInf = 1 << 20;
int dtime[101][101];
int dcost[101][101];
 
int n, m;
 
void wf() {
    for(int k = 1; k <= m; k++)
        for(int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++) {
                dtime[i][j] = min(dtime[i][j], dtime[i][k] + dtime[k][j]);
                dcost[i][j] = min(dcost[i][j], dcost[i][k] + dcost[k][j]);
            }
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    while (cin >> n >> m, n || m) {
        fill(dtime[0], dtime[101], kInf);
        fill(dcost[0], dcost[101], kInf);
        for (int i = 0; i < 101; i++)
            dtime[i][i] = dcost[i][i] = 0;
        for (int i = 0; i < n; i++) {
            int a, b, cost, time;
            cin >> a >> b >> cost >> time;
            dtime[a][b] = dtime[b][a] = time;
            dcost[a][b] = dcost[b][a] = cost;
        }
        wf();
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            int p, q, r;
            cin >> p >> q >> r;
            if(r)
                cout << dtime[p][q] << endl;
            else
                cout << dcost[p][q] << endl;
        }
    }
}

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

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main() {
  int n, m;
  while(cin >> n >> m, n+m) {
    pii dp[110][110];
    rep(i, m+1) rep(j, m+1) dp[i][j].first = dp[i][j].second = 1<<25;
    while(n--) {
      int a, b, cost, time; cin >> a >> b >> cost >> time;
      dp[a][b].first = dp[b][a].first = cost;
      dp[a][b].second = dp[b][a].second = time;
    }

    rep(i, m+1) dp[i][i].first = dp[i][i].second = 0;

    rep(k, m+1) rep(i, m+1) rep(j, m+1) {
      dp[i][j].first = min(dp[i][j].first, dp[i][k].first + dp[k][j].first);
      dp[i][j].second = min(dp[i][j].second, dp[i][k].second + dp[k][j].second);
    }
      
    int k; cin >> k;
    rep(i, k) {
      int p, q, r; cin >> p >> q >> r;
      if(r == 0) cout << dp[p][q].first << endl;
      else cout << dp[p][q].second << endl;
    }
  }
}

C++: #include<iostream>

using namespace std;

const int inf = 1e8;

int d[201][201][2];
int E,V;

int main(){
  while(cin>> E >> V,E+V){
    for(int i = 0 ;  i < V ; i ++)
      for(int j = 0 ; j < V ; j ++){
	d[i][j][0] = inf;
	d[i][j][1] = inf;
      }
    int s,t,c,ti;
    for(int i = 0 ; i < E ; i ++){
      cin>>s>>t>>c>>ti;
      s--; t--;
      d[s][t][0] = c;
      d[s][t][1] = ti;
    
      d[t][s][0] = c;
      d[t][s][1] = ti;
    }
    
    for(int k=0; k < V; k++){
        for(int i=0; i < V; i++){
            for(int j=0; j < V; j++){
                d[i][j][1] = min(d[i][j][1], d[i][k][1] + d[k][j][1]);
                d[i][j][0] = min(d[i][j][0], d[i][k][0] + d[k][j][0]);
            }
        }
    }

    int num;
    cin>>num;
    for(int i = 0 ; i < num ; i ++){
      int start , terminus , version;
      cin>>start >> terminus >> version;
      start -- ; terminus --;
      cout<<(version?d[start][terminus][1]:d[start][terminus][0]) <<endl;
    }
  }
}

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

const int MAX=100;
using namespace std;
int main(){
  int n,m;
  int i,j,k;
  int a,b,co,ti;
  int x;
  int home1[MAX][MAX];
  int home2[MAX][MAX];
  int p,q,r;
  while(1){
    cin >> n >> m;
    if(n==0 && m==0)break;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	home1[i][j]=9999;
	home2[i][j]=9999;
      }
    }
    for(i=0;i<n;i++){
      cin >> a >> b >> co >> ti;
      home1[a-1][b-1]=home1[b-1][a-1]=co;
      home2[a-1][b-1]=home2[b-1][a-1]=ti;
    }
    for(k=0;k<n;k++){
      for(i=0;i<n;i++){
	for(j=0;j<n;j++){
	  home1[i][j]=min(home1[i][j],home1[i][k]+home1[k][j]);
	  home2[i][j]=min(home2[i][j],home2[i][k]+home2[k][j]);
	}
      }
    }
    cin >> x;
    for(int l=0;l<x;l++){
      cin >> p >> q >> r;
      if(r==0){
	cout << home1[p-1][q-1] << endl;
      }else{
	cout << home2[p-1][q-1] << endl;
      }
    }
  }
}