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>

using namespace std;

void search(int,int,int);

int	n,m,**lns[2];
unsigned int *val;
bool	*uvtd;

int main(void){
	int	K;

	do{
		cin >> n >> m;

		if(n!=0||m!=0){
			for(int i=0;i<2;i++){
				lns[i] = new int*[m+1];
				for(int j=1;j<=m;j++){
					lns[i][j] = new int[n];
					for(int k=0;k<n;k++)
						lns[i][j][k]=0;
				}
			}
			val = new unsigned int[m+1];
			uvtd = new bool[m+1];

			for(int i=0;i<n;i++){
				int a,b,cost,time;
				cin >> a >> b >> cost >> time;
				lns[0][a][i]=lns[0][b][i]=cost;
				lns[1][a][i]=lns[1][b][i]=time;
			}

			cin >> K;
			for(int i=0;i<K;i++){
				int p,q,r;
				cin >> p >> q >> r;
				for(int j=1;j<=m;j++){
					val[j]=-1;
					uvtd[j]=true;
				}
				val[p]=0;
				search(p,q,r);
				cout << val[q] << endl;
			}

			for(int i=0;i<2;i++){
				for(int j=1;j<=m;j++)
					delete [] lns[i][j];
				delete [] lns[i];
			}
			delete [] val;
			delete [] uvtd;
		}
	}while(n!=0||m!=0);
	return 0;
}

void search(int sta,int fin,int mode){
	uvtd[sta]=false;
	for(int i=0;i<n;i++)
		if(lns[mode][sta][i]){
			for(int j=1;j<=m;j++)
				if(uvtd[j]&&lns[mode][j][i]){
					if(val[sta]+lns[mode][sta][i]<val[j])
						val[j]=val[sta]+lns[mode][sta][i];
					if(j!=fin){
						search(j,fin,mode);
						uvtd[j]=true;
					}
				}
		}

}

C++: #include <iostream>
#include <vector>
#include <map>
#include <limits.h>
#include <queue>


#define INF INT_MAX

using namespace std;


struct edge {int to,cost;};
typedef pair<int,int> P;

vector<edge> ek[3002];
vector<edge> em[3002];
priority_queue<P,vector<P>,greater<P> >que;

int d[102];
int q,r;

void dik()
{
  while(!que.empty())
    {
      P p = que.top();
      que.pop();
      // cout<<p.first<<"  "<<p.second<<endl;
      int v=p.second;
      int h=p.first;
      if(v==q && d[v]!=INF)
	break;
      for(int i=0;i<ek[v].size();i++)
	{
	  edge e;
	  if(r==0)
	    e=em[v][i];
	  else
	    e=ek[v][i];
	  if(d[e.to]>d[v] + e.cost)
	    {
	      d[e.to]=d[v]+e.cost;
	      que.push(P(d[e.to],e.to));
	    }
	  
	}
    }
  
}

int main()
{
  int n,m;
  for(;cin>>n>>m,n;)
    {
      //マップ初期化
      for(int i=0;i<3003;i++)
	{
	  ek[i].clear();
	  em[i].clear();
	}
      
      for(int i=0;i<n;i++)
	{
	//エッジ情報
	  int a,b,cost,time;
	  cin>>a>>b>>cost>>time;
	  edge xx;
	  xx.to=b;
	  xx.cost=cost;
	  em[a].push_back(xx);
	  xx.cost=time;
	  ek[a].push_back(xx);

	  xx.to=a;
	  xx.cost=cost;
	  em[b].push_back(xx);
	  xx.cost=time;
	  ek[b].push_back(xx);

	  
	}
      int c;
      cin>>c;
      for(;c--;)
	{
	  fill(d,d+102,INF);
	  //問い合わせ
	  int p;
	  cin>>p>>q>>r;
	  d[p]=0;
	  que.push(P(0,p));
	  dik();
	  cout<<d[q]<<endl;
	}
    }
}

C++: #include<iostream>
using namespace std;
#include<algorithm>
#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(k,m){
		REP(i,m){
	 		REP(j,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<algorithm>

using namespace std;
int time[3001][3001];
int cost[3001][3001];


int main(){
	
	int i,j,k,a,b,t,c;
	int rail, station;
	int q,start,goal,dotti;
	int temp;
	
	


	while (1){
		
		cin >> rail >> station;
		
		if (rail == 0 && station == 0){
			break;
		}


		for (i = 0; i < station+1; i++){
			for (j = 0; j < station+1; j++){
				time[i][j] = 1000000;
				cost[i][j] = 1000000;
			}
		}

		for (i = 0; i < rail; i++){
			cin >> a >> b >> c >> t;
			time[a][b] = t;
			time[b][a] = t;
			cost[a][b] = c;
			cost[b][a] = c;
		}


		cin >> q;

		for (;q>0;q--){
			cin >> start >> goal >> dotti;

			for (k = 1; k <= station; k++){
				for (i = 1; i <= station; i++){
					for (j = 1; j <= station; j++){
						cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
					}
				}
			}

			for (k = 1; k <= station; k++){
				for (i = 1; i <= station; i++){
					for (j = 1; j <= station; j++){
						time[i][j] = min(time[i][j], time[i][k] + time[k][j]);
					}
				}
			}


			if (dotti == 0){
				cout << cost[start][goal] << endl;
			}

			if (dotti == 1){
				cout << time[start][goal] << endl;
			}


		}
	


	}



}