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]
					t_newlen := t_dist[i][k] + t_dist[k][j]
					if c_newlen < c_dist[i][j] {
						c_dist[i][j] = c_newlen
						c_prev[i][j] = c_prev[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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF (1<<29)

int main(){
  int time[101][101], cost[101][101];
  int n, m;
  int from, to, Cost, Time;
  
  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    for(int i = 1 ; i <= m ; i++){
      for(int j = 1 ; j <= m ; j++){
	if(i == j) time[i][j] = cost[i][j] = 0;
	else time[i][j] = cost[i][j] = INF;
      }
    }
    
    while(n--){
      cin >> from >> to >> Cost >> Time;
      cost[from][to] = cost[to][from] = Cost;
      time[from][to] = time[to][from] = Time;
    }
    
    for(int k = 1 ; k <= m ; k++){
      for(int i = 1 ; i <= m ; i++){
	for(int j = 1 ; j <= m ; j++){
	  cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
	  time[i][j] = min(time[i][j], time[i][k]+time[k][j]);
	}
      }
    }
    int num;
    cin >> n;
    while(n--){
      cin >> from >> to >> num;
      if(num == 0) cout << cost[from][to] << endl;
      else cout << time[from][to] << endl;
    }
  }
  return 0;
}

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

array<array<int, 210>, 210> costs;
array<array<int, 210>, 210> times;

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        for (auto& ar : costs) ar.fill(1000000);
        for (auto& ar : times) ar.fill(1000000);
        for (int i = 0; i < n; i++) {
            int a, b, c, t;
            cin >> a >> b >> c >> t;
            a--; b--;
            costs[a][b] = costs[b][a] = c;
            times[a][b] = times[b][a] = t;
        }
        for (int i = 0; i < n; i++) {
            costs[i][i] = 0;
            times[i][i] = 0;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    costs[j][k] = min(costs[j][k], costs[j][i] + costs[i][k]);
                    times[j][k] = min(times[j][k], times[j][i] + times[i][k]);
                }
            }
        }
        int k;
        for (cin >> k; k; k--) {
            int p, q, r;
            cin >> p >> q >> r;
            p--; q--;
            if (r == 0) {
                cout << costs[p][q] << endl;
            }
            else {
                cout << times[p][q] << endl;
            }
        }
    }
    return 0;
}

C++: #include<iostream>
using namespace std;
#include<algorithm>
#include<string>
#define REP(i,a) for(int  i=0;i<a;i++)
int A[101][101];
int B[101][101];
int main(){
	int a,b=0,c=0,d,n,m;	
	cin>>n>>m;
	while(n!=0||m!=0){
	REP(i,m){
		REP(j,m){
			A[i][j]=1001;
			B[i][j]=1001;
		}
	}
	REP(i,n){
	cin>>a>>b>>c>>d;
	A[a-1][b-1]=c;
	B[a-1][b-1]=d;	
	A[b-1][a-1]=c;
	B[b-1][a-1]=d;
	}
	REP(i,m){
		REP(j,m){
		if(i==j) continue;
	 		REP(k,m){
		A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
		B[i][j]=min(B[i][j],B[i][k]+B[k][j]);
		A[j][i]=A[i][j];
		B[j][i]=B[i][j];		
			}
		}	
	}
	cin>>n;
	REP(i,n){
	cin>>a>>b>>c;
	if(c==0) cout<<A[a-1][b-1]<<endl;
	else cout<<B[a-1][b-1]<<endl;
	}
	cin>>n>>m;
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>P;
int Start,End;
const int INF=100000000;
struct edge{
    int to,cost;
    edge(int a,int b){
        to=a;cost=b;
    }
    edge(){}
};
int dijkstra(vector<vector<edge> >V){
    priority_queue<P,vector<P>,greater<P> >Q;
    int d[100];
    fill(d,d+100,INF);
    d[Start]=0;
    Q.push(P(0,Start));

    while(Q.size()){
        P p=Q.top();Q.pop();
        int v=p.second;
        if(d[v]<p.first)continue;
        for(int i=0;i<V[v].size();i++){
            int to=V[v][i].to;
            int cost=V[v][i].cost;
            if(d[to]>d[v]+cost){
                d[to]=d[v]+cost;
                Q.push(P(d[to],to));
            }
        }
    }
    return d[End];
}
int main(){
    int n,m;
    while(cin>>n>>m,n||m){
        vector<vector<edge> >V[2];
        V[0].resize(m);V[1].resize(m);
        while(n--){
            int a,b,cost,time;
            cin>>a>>b>>cost>>time;a--;b--;
            V[0][a].push_back(edge(b,cost));
            V[0][b].push_back(edge(a,cost));

            V[1][a].push_back(edge(b,time));
            V[1][b].push_back(edge(a,time));
        }
        int k;
        cin>>k;
        while(k--){
            int r;
            cin>>Start>>End>>r;Start--;End--;
            cout<<dijkstra(V[r])<<endl;
        }
    }
    return 0;
}