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<stdio.h>
#define INF 1000000
typedef struct{
	short to,cost,time;
}edge;
int n,m;
int i,j,k;
int p,q,r;
edge e[100][3000];
int ce[100];
bool used[100];
int d[100];

int min(int a,int b){return a<b?a:b;}

int solve(int p,int q,int r){
	int l;
	for(l=0;l<m;l++){
		used[l]=false;
		d[l]=INF;
	}
	d[p]=0;
	int next;
	while(1){
		next=-1;
		for(l=0;l<m;l++){
			if(!used[l]&&(next==-1||d[next]>d[l]))next=l;
		}
		if(next==-1)break;
		used[next]=true;
		for(l=0;l<ce[next];l++){
			if(r==0)d[e[next][l].to]=min(d[e[next][l].to],d[next]+e[next][l].cost);
			if(r==1)d[e[next][l].to]=min(d[e[next][l].to],d[next]+e[next][l].time);
		}
	}
	return d[q];
}

int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)return 0;
		for(i=0;i<m;i++)ce[i]=0;
		for(i=0;i<n;i++){
			int a,b,cost,time;
			scanf("%d %d %d %d",&a,&b,&cost,&time);
			e[a-1][ce[a-1]].to=b-1;
			e[a-1][ce[a-1]].cost=cost;
			e[a-1][ce[a-1]].time=time;
			ce[a-1]++;
		}
		scanf("%d",&k);
		int ans_c=INF,ans_t=INF;
		for(i=0;i<k;i++){
			scanf("%d %d %d",&p,&q,&r);
			if(r==0)ans_c=min(ans_c,solve(p-1,q-1,r));
			if(r==1)ans_t=min(ans_t,solve(p-1,q-1,r));
		}
		printf("%d\n%d\n",ans_c,ans_t);
	}
}

C++: #include<iostream>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
int main(void){
  int maze[2][100][100];
  int n,m;
  int a,b,c,t;
  while(cin>>m>>n,n+m){
    rep(i,n)rep(j,n)rep(k,2)maze[k][i][j]=100000;
    rep(i,m){
      cin>>a>>b>>c>>t;
      maze[0][--a][--b]=c;
      maze[1][a][b]=t;
      maze[0][b][a]=c;
      maze[1][b][a]=t;
    }
    rep(k,n)rep(i,n)rep(j,n)rep(l,2)
      maze[l][i][j]=min(maze[l][i][j],maze[l][i][k]+maze[l][k][j]);
    cin>>m;
    //cout<<endl;rep(i,n)rep(j,n)cout<<maze[1][i][j]<<(j==n-1?'\n':' ');
    
    rep(i,m){
      cin>>a>>b>>c;
      cout<<maze[c][--a][--b]<<endl;
    }
  }
}

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

#define MAX 256
#define INF 1000000

struct edge {
	int money;
	int time;
};

int main(){
	int n, m;
	int count;
	edge G[120][120];

	while(cin >> n >> m, n || m){
		for(int i=0; i < 120; i++){
			for(int j=0; j < 120; j++){
				G[i][j].money = INF;
				G[i][j].time = INF;
			}
		}
		for(int i=0; i < 120; i++){
			G[i][i].money = 0;
			G[i][i].time = 0;
		}

		for(int i=0; i < n; i++){
			int a, b, mo, t;
			cin >> a >> b >> mo >> t;

			G[a][b].time=t;
			G[a][b].money=mo;
			G[b][a].time=t;
			G[b][a].money=mo;
		}

		for(int k=0; k < n; k++){
			for(int i=0; i < n; i++){
				for(int j=0; j < n; j++){
					G[i][j].time = min(G[i][j].time, G[i][k].time+G[k][j].time);
					G[i][j].money = min(G[i][j].money, G[i][k].money+G[k][j].money);
				}
			}
		}

		cin >> count;
		for(int i=0; i < count; i++){
			int p;
			cin >> n >> m >> p;

			if(p) cout << G[n][m].time << endl;
			else cout << G[n][m].money << endl;
		}
	}

}

C++: #include<cstdio>
#include<iostream>
#include<queue>

#define NMAX 3000
#define MMAX 100
#define INF 1000*MMAX+100
using namespace std;

int main(void){

	int n,m;
	int a[NMAX],b[NMAX],cost[2][NMAX];
	int k;
	int p,q,r;
	int node[MMAX];
	queue<int> now;

	while(1){
		cin>>n>>m;
		if(n==0||m==0) break;
		for(int i=0;i<n;i++){
			cin>>a[i]>>b[i]>>cost[0][i]>>cost[1][i];
		}
		cin>>k;
		for(int i=0;i<k;i++){
			cin>>p>>q>>r;

			for(int i=0;i<MMAX;i++) node[i]=INF;
			now.push(p);
			node[p]=0;

			while(!now.empty()){
				for(int j=0;j<n;j++){
					if(a[j]==now.front()){
						if(node[b[j]]>node[a[j]]+cost[r][j]){
							now.push(b[j]);
							node[b[j]]=node[a[j]]+cost[r][j];
						}
					}
					if(b[j]==now.front()){
						if(node[a[j]]>node[b[j]]+cost[r][j]){
							now.push(a[j]);
							node[a[j]]=node[b[j]]+cost[r][j];
						}
					}
				}
				now.pop();
			}
			cout<<node[q]<<endl;
		}
	}

	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)

template<typename T>
void remove(vector<T>& vector, unsigned int index){
vector.erase(vector.begin() + index);
}

typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void){
	int n, m;
	while(cin >> n >> m, n||m){
		int cost[120][120];
		int timm[120][120];
		fill_n(*cost, 120*120, 10000000);
		fill_n(*timm, 120*120, 10000000);
		for(int i = 0; i < n; i++){
			int a, b,c,t;
			cin >> a >> b >> c >> t;
			cost[a][b] = c;
			cost[b][a] = c;
			timm[a][b] = t;
			timm[b][a] = t;
		}
		for(int k=0;k<n;++k)for(int i=0;i<n;++i)for(int j=0;j<n;++j){
			cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			timm[i][j] = min(timm[i][j], timm[i][k] + timm[k][j]);
		}
		int k;
		cin >> k;
		rep(i, k){
			int a, b, c;
			cin >> a >> b >> c;
			if(!c)
				cout << cost[a][b] << endl;
			else
				cout << timm[a][b] << endl;
		}
	}

	return 0;
}