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 <bits/stdc++.h>
using namespace std;
#define INFTY (1<<21)
#define MAX 100
void floyd(int m, int C[MAX][MAX], int T[MAX][MAX]) {
	for (int k = 0; k < m; k++)
		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++) {
				C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
				T[i][j] = min(T[i][j], T[i][k] + T[k][j]);
			}
}
main() {
	int n, m, a, b, c, t, k, q, C[MAX][MAX], T[MAX][MAX];
	while( cin >> n >> m && !(n == 0 && m == 0) ) {
		for(int i = 0;i<m;i++)
		for(int j = 0;j<m;j++) {C[i][j] = T[i][j] = INFTY;}
		for(int i = 0;i<n;i++) {
			cin >> a >> b >> c >> t; C[a-1][b-1] = C[b-1][a-1] = c; T[a-1][b-1] = T[b-1][a-1] = t;
		}
		floyd(m, C, T);
		cin >> k;
		for(int i = 0;i<k;i++) {
			cin >> a >> b >> q;
			if ( q ) cout << T[a-1][b-1] << endl;
			else cout << C[a-1][b-1] << endl;}
	}
}

C++: #include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int road1[111][111];
  int road2[111][111];
  int n,m;
  int a,b,cost,time;
  int p,q,r;
  int x;
  while(1){
    for(int i=0;i<101;i++){
      for(int j=0;j<101;j++){
	road1[i][j]=road2[i][j]=1111111;
      }
    }
    cin >> n >> m;
    if(n==0 && m==0)break;
    for(int i=0;i<n;i++){
      cin >> a >> b >> cost >> time;
      road1[a-1][b-1]=road1[b-1][a-1]=cost;
      road2[a-1][b-1]=road2[b-1][a-1]=time;
    }

    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	  if(road1[i][j]>road1[i][k]+road1[k][j]){
	    road1[i][j]=road1[i][k]+road1[k][j];
	  }
	  if(road2[i][j]>road2[i][k]+road2[k][j]){
	    road2[i][j]=road2[i][k]+road2[k][j];
	  }
	}
      }
    }
    
    cin >> x;
    for(int i=0;i<x;i++){
      cin >> p >> q >> r;
      cout << (r==0 ? road1[p-1][q-1] : road2[p-1][q-1]) << endl;
    }
  }
}

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

const int INF = 1000000000;

int main()
{
	while(true){
		int n, m;	//線路の情報の数n, 駅の数m
		cin >> n >> m;

		if(n==0 && m==0)
			break;

		int C[100][100];	//costのグラフ
		int T[100][100];	//timeのグラフ
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				if(i==j){
					C[i][j] = T[i][j] = 0;		//対角線は0
				}
				else{
					C[i][j] = T[i][j] = INF;    
				}
			}
		}

		for(int i=0; i<n; i++){
			int a, b, c, t;		//線路の情報a,bとcost,time
			cin >> a >> b >> c >> t;

			C[a-1][b-1] = C[b-1][a-1] = c;
			T[a-1][b-1] = T[b-1][a-1] = t;
		}

		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					if(C[j][k]>C[j][i]+C[i][k])
						C[j][k] = C[j][i]+C[i][k];
				}
			}
		}

		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					if(T[j][k]>T[j][i]+T[i][k])
						T[j][k] = T[j][i]+T[i][k];
				}
			}
		}

		int k;	//問い合わせの数
		cin >> k;
		for(int i=0;i<k;i++){
			int p, q, r;	//出発駅p, 到着駅q, 値の種類r
			if(r)	//r==1なら最短時間
				cout << T[p-1][r-1] << endl;
			else
				cout << C[p-1][r-1] << endl;
		}
	}

	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
static const int INFTY = (1 << 21);
int main(){
	int t[102][102];int c[102][102];
	int n,m,a,b,cost,time,kk,p,q,r;
	while(cin >> n >> m,n,m){
		for(int i=1;i<102;i++){
			for(int j=1;j<102;j++){
				t[i][j] = c[i][j] = INFTY;
			}
		} 
		for(int i = 0;i < n;i++){
			cin >> a >> b >> cost >> time;
			t[a][b] = time;
			c[a][b] = cost;
		}
		for(int k=1;k<=m;k++){
			for(int i=1;i<=m;i++){
				if(t[i][k] == INFTY) continue;
				for(int j=1;j<=m;j++){
					if(t[i][k] == INFTY) continue;
					t[i][j] = min(t[i][j],t[i][k]+t[k][j]);
					c[i][j] = min(c[i][j],c[i][k]+c[k][j]);
				}
			}
		}
		cin >>  kk;
		for(int i=0;i<kk;i++){
			cin >> p >> q >> r;
			if(r == 0) cout << c[p][q] << endl;
			else cout << t[p][q] << endl;
		}
	}
	return 0;
}

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

static const int MAX_ST = 100;
static const int INFTY  = ( 1 << 25 );

pair< int, int > AdjMt[MAX_ST][MAX_ST];	// first : cost, second : time

int Min( const int& left, const int& right ) { return left > right ? right : left; }

int main()
{

	ios::sync_with_stdio( false );	// for speeding up

	int  info_n, sta_n, query_n, depplc, dest, cost, time;
	bool query_meth;

	while( cin >> info_n >> sta_n, info_n || sta_n ) {

		for( int i = 0; i < MAX_ST; i++ ) {
			for( int j = 0; j < MAX_ST; j++ ) AdjMt[i][j].first = AdjMt[i][j].second = INFTY;
		}

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

			cin >> depplc >> dest >> cost >> time;
			AdjMt[--depplc][--dest].first = cost;
			AdjMt[depplc][dest].second    = time;

		}

		// Warshall-Floyd
		for( int k = 0; k < sta_n; k++ ) {
			for( int i = 0; i < sta_n; i++ ) {
				for( int j = 0; j < sta_n; j++ ) {

					if( AdjMt[i][j].first == INFTY && AdjMt[i][k].first == INFTY && AdjMt[k][j].first == INFTY ) continue;

					AdjMt[i][j].first  = Min( AdjMt[i][j].first , AdjMt[i][k].first  + AdjMt[k][j].first );
					AdjMt[i][j].second = Min( AdjMt[i][j].second, AdjMt[i][k].second + AdjMt[k][j].second );

				}
			}
		}

		cin >> query_n;
		for( int i = 0; i < query_n; i++ ) {

			cin >> depplc >> dest >> query_meth;
			depplc--; dest--;
			cout << ( !query_meth ? AdjMt[depplc][dest].first : AdjMt[depplc][dest].second ) << endl;

		}

	}

	return 0;

}