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
			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<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

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

const int MAXN = 301, MAXM = 101, INF = 1000000 ;
const int TIME = 1, COST = 0;

int cost[2][MAXM][MAXM];
int d[MAXM];
int used[MAXM];
int a, b, c, t, p, q, r, k;
int n, m;

int main()
{
    while(cin >> n >> m && n)
    {
        memset(cost, INF, sizeof(cost));

        REP(n)
        {
            cin >> a >> b >> c >> t;
            a--; b--;
            cost[COST][a][b] = cost[COST][b][a] = c;
            cost[TIME][a][b] = cost[TIME][b][a] = t;
        }

        cin >> k;
        REP(k)
        {
            cin >> p >> q >> r; p--; q--;

            memset(d, INF , sizeof(d));
            memset(used, false, sizeof(used));
            d[p] = 0;

            while(1)
            {
                int v = -1;
                rep(j,m)if(!used[j] &&(v == -1 || d[j] < d[v])) v = j;

                if(v == -1) break;
                used[v] = true;

                rep(j,m)d[j] = min(d[j], d[v] + cost[r][v][j]);
            }
            cout << d[q] << endl;
        }
    }
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define INF 1e9

struct WarshallFloyd {
  vector<vector<int>> d;
  int v;

  WarshallFloyd(int n) : v(n), d(n, vector<int>(n, INF)) {
    for(int i = 0; i < v; ++i) d[i][i] = 0;
  }

  void add(int from, int to, int cost) {
    d[from][to] = cost;
    d[to][from] = cost;
  }

  void make() {
    for(int k = 0; k < v; ++k) {
      for(int i = 0; i < v; ++i) {
        for(int j = 0; j < v; ++j) {
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
      }
    }
  }

  int dist(int i, int j) {
    return d[i][j];
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  while(cin >> n >> m, n != 0 && m != 0) {
    WarshallFloyd cost(m), time(m);
    for(int i = 0; i < n; ++i) {
      int a, b, c, t;
      cin >> a >> b >> c >> t;
      a--; b--;
      cost.add(a, b, c);
      time.add(a, b, t);
    }

    cost.make();
    time.make();
    int k;
    cin >> k;
    for(int i = 0; i < k; ++i) {
      int p, q, r;
      cin >> p >> q >> r;
      p--; q--;
      if(r == 0) cout << cost.dist(p, q) << endl;
      else cout << time.dist(p, q) << endl;
    }
  }
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<queue>

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

using namespace std;

int n,m;

struct edge {
public:
	int to,cost,time;
	edge(int b,int cost,int time) {
		this->to = b;
		this->cost = cost;
		this->time = time;
	}
};

typedef pair<int,int> P;

vector<edge> G[3007];

int dijk(int s,int t,int mode) {
	
	priority_queue<P, vector<P> ,greater<P> > que;
	int d[3007];rep(i,3007) d[i]=1000000;
	d[s]=0;
	que.push(P(0,s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if(v==t) break;
		if(d[v] < p.first) continue;

		rep(i,G[v].size()) {
			edge e = G[v][i];
			int cost = mode==0?e.cost:e.time;

			if(d[e.to] > d[v] + cost) {
				d[e.to] = d[v] + cost;
				que.push(P(d[e.to],e.to));
			}

		}
	}
	return d[t];
}

void solve() {
	rep(i,n) {
		int a,b,cost,time;
		cin>>a>>b>>cost>>time;
		G[a].push_back(edge(b,cost,time));
		G[b].push_back(edge(a,cost,time));
	}

	int k;
	cin>>k;
	rep(i,k) {
		int s,t,mode;
		cin>>s>>t>>mode;
		cout<<dijk(s,t,mode)<<endl;
	}

	rep(i,3007) G[i].clear();
}

int main() {
	while (cin>>n>>m)
	{
		if(n+m==0) return 0;
		solve();
	}
	return 0;
}

C++: #define _USE_MATH_DEFINES
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int N, M, K;
	int cost[100][100], time[100][100];
	while(cin >> N >> M, N || M){
		fill_n( (int*)cost, 100*100, 1e6 );
		fill_n( (int*)time, 100*100, 1e6 );
		int A, B;
		for(int i = 0; i < N; i++){
			cin >> A >> B;
			A--; B--;
			cin >> cost[A][B] >> time[A][B];
			cost[B][A] = cost[A][B]; time[B][A] = time[A][B];
		}
		
		for(int k = 0; k < M; k++){
			for(int i = 0; i < M; i++){
				for(int j = 0; 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] );
				}
			}
		}

		cin >> K;
		int P, Q, R;
		for(int i = 0; i < K; i++){
			cin >> P >> Q >> R; P--; Q--;
			if(R == 0) printf("\t%d\n", cost[P][Q] );
			else printf("\t%d\n", time[P][Q] );
		}
	}
	return 0;
}