题目链接如下：
http://acm.hdu.edu.cn/showproblem.php?pid=3790
这题用最短路径Djikstra就可以解决，用Floyd会超时！
代码如下：
#include <iostream>
using namespace std;
const int INF = 999999999;
const int N = 1001;
struct
{
int distance;
int price;
} map[N][N];
int dist[N];
int price[N];
int visited[N];
void djikstra(int s, int t, int n);
int main()
{
int n, m;
int i, j, a, b, d, p;
int s, t;
while(scanf("%d%d", &n, &m) != EOF && (n || m))
{
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
map[i][j].distance = INF;
map[i][j].price = INF;
}
}
for(i = 1; i <= n; i++)
{
map[i][i].distance = 0;
map[i][i].price = 0;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d%d%d", &a, &b, &d, &p);
if(map[a][b].distance > d)
{
map[a][b].distance = map[b][a].distance = d;
map[a][b].price = map[b][a].price = p;
}
}
scanf("%d%d", &s, &t);
djikstra(s, t, n);
}
return 0;
}
void djikstra(int s, int t, int n)
{
int i, j;
int min, k;
memset(visited, 0, sizeof(visited));
for(i = 1; i <= n; i++)
{
dist[i] = map[s][i].distance;
price[i] = map[s][i].price;
}
visited[s] = 1;
for(i = 1; i <= n; i++)
{
min = INF;
for(j = 1; j <= n; j++)
{
if(!visited[j] && dist[j] < min)
{
min = dist[j];
k = j;
}
}
if(min == INF)
{
break;
}
visited[k] = 1;
for(j = 1; j <= n; j++)
{
if(!visited[j])
{
if(dist[j] > dist[k] + map[k][j].distance)
{
dist[j] = dist[k] + map[k][j].distance;
price[j] = price[k] + map[k][j].price;
}
else if(dist[j] == dist[k] + map[k][j].distance)
{
if(price[j] > price[k] + map[k][j].price)
{
price[j] = price[k] + map[k][j].price;
}
}
}
}
}
printf("%d %d\n", dist[t], price[t]);
}