Go: // Warshall–Floyd Algorithm

package main

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

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
					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++: #include<iostream>
#include<queue>
#include<vector>
#include<limits>

using namespace std;

struct RequestObj {
	int begin, end, type;
};

int n, m;//???,???????????°
int k;//????????¨????????°
int time_table[100][100];
int cheap_table[100][100];
RequestObj request[200];


const int INF = 100000000;

int main() {
	while (cin >> n >> m, n * m) {

		for (int i = 0; i < m; i++)for (int j = 0; j < m; j++)time_table[i][j] = INF, cheap_table[i][j] = INF;
		
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			cin >> cheap_table[a - 1][b - 1] >> time_table[a - 1][b - 1];
		}
		cin >> k;
		for (int i = 0; i < k; i++) {
			cin >> request[i].begin >> request[i].end >> request[i].type;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < m; k++) {
					if (cheap_table[j][i] + cheap_table[i][k] < cheap_table[j][k]) {
						cheap_table[j][k] = cheap_table[j][i] + cheap_table[i][k];
					}
				}
			}
		}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < m; k++) {
					if (time_table[j][i] + time_table[i][k] < time_table[j][k]) {
						time_table[j][k] = time_table[j][i] + time_table[i][k];
					}
				}
			}
		}
		for (int i = 0; i < k; i++) {
			if (request[i].type == 0) {
				cout << cheap_table[request[i].begin - 1][request[i].end - 1] << endl;
			}
			else {
				cout << time_table[request[i].begin - 1][request[i].end - 1] << endl;
			}
		}

		for (int i = 0; i < m; i++)for (int j = 0; j < m; j++)time_table[i][j] = INF, cheap_table[i][j] = INF;

	}
	return 0;
}

C++: #include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define IREP(it,array) for(vector<int>::iterator it=array.begin(); it!=array.end(); ++it)
#define SREP(it,array) for(vector<string>::iterator it=array.begin(); it!=array.end(); ++it)

#define MP       make_pair
#define PB       push_back
#define ALL(x)   (x).begin(),(x).end()

const int INF = 1<<29;
const double EPS = 1e-9;
double zero(double d){
  return d < EPS ? 0.0 : d;
}

typedef long long LL;
typedef pair<int,int> P;


int main()
{
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(7);

  int n,m;
  while(cin >> n >> m){
    if(n==0&&m==0)
      return 0;

    vector< vector<int> > cost(m+1, vector<int>(m+1,INF)),
      time(m+1, vector<int>(m+1,INF));

    REP(i,cost.size()){
      cost[i][i] = time[i][i] = 0;
    }

    REP(i,n){
      int a,b,c,t;
      cin >> a >> b >> c >> t;
      cost[a][b] = cost[b][a] = c;
      time[a][b] = time[b][a] = t;
    }

    REP(i,cost.size()){
      REP(j,cost.size()){
	REP(k,cost.size()){
	  cost[j][k] = min( cost[j][k], cost[j][i] + cost[i][k] );
	  time[j][k] = min( time[j][k], time[j][i] + time[i][k] );
	}
      }
    }

    int k;
    cin >> k;
    REP(_tmp,k){
      int p,q,r;
      cin >> p >> q >> r;
      int res= r ? time[p][q] : cost[p][q];
      cout << res << endl;
    }
  }

  return 0;
}

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

#define INF (1LL << 63)
struct edge{
    size_t to;
    size_t weight;
};

vector<size_t> dijkstra(vector<vector<edge>>& Graph, int& startPoint, int& vertexNum){
    vector<size_t> minimumWeight(vertexNum,INF);
    priority_queue<vector<pair<size_t,size_t>>, vector<pair<size_t,size_t>>, greater<pair<size_t,size_t>>> priorityQueue;
    priorityQueue.push({0,startPoint});
    minimumWeight[startPoint] = 0;
    while(!priorityQueue.empty()){
        pair<size_t,size_t> tmp = priorityQueue.top();
        edge Edge;
        Edge.to = tmp.second;
        Edge.weight = tmp.first;
        priorityQueue.pop();
        if(minimumWeight[Edge.to] < Edge.weight) continue;
        for(edge& edge : Graph[Edge.to]){
            if(minimumWeight[edge.to] < minimumWeight[Edge.to] + edge.weight) continue;
            minimumWeight[edge.to] = minimumWeight[Edge.to] + edge.weight;
            priorityQueue.push({minimumWeight[edge.to],edge.to});
        }
    }
    return minimumWeight;
}


int main(){
    int N,M;
    while(cin >> N >> M, N&&M){
        vector<vector<edge>> costGraph(M);
        vector<vector<edge>> timeGraph(M);

        for(int i = 0;i < N; i++){
            size_t a,b,c,t;
            cin >> a >> b >> c >> t;
            a--,b--;

            costGraph[a].push_back({b,c});
            costGraph[b].push_back({a,c});

            timeGraph[a].push_back({b,t});
            timeGraph[b].push_back({a,t});
        }

        int k;
        cin >> k;
        for(int j=0;j<k;j++){
            int p,q,r;
            cin >> p >> q >> r;
            p--, q--;
            vector<size_t> res;
            if(r == 0) res = dijkstra(costGraph, p, M);
            else res = dijkstra(timeGraph, p, M);   

            cout << res[q] << endl;        
        }
    }
}