题目链接：http://acm.swust.edu.cn/problem/842/
Time limit(ms): 1000 Memory limit(kb): 10000
Description
2012新的暑期集训开始了，一切都还相当不错，但是有一个问题成为了同学们的难题，那就是从实验室到食堂时，天气是非常的炎热，以至于大家都尽量避免从没有遮阴的地方走过，但是某些路径又不得不从没有遮阴的地方走过，所以现在难题出来了，给予你一些单向路段，让你找出从实验室到食堂，晒太阳最少的路径长度，以及该条路径的总长度。如果存在多条最少晒太阳的路径，则总长度要求最短。
输入n和m，表明是有n<=1000个转折点，m条路径，然后输入m(m<=100000)条路径，每一条路径包括4个数据，s，e，dis1 ， dis2，分别表示该条路径的起点，
终点，路径总长度，以及没有遮阴路径的长度(dis1>=dis2)；
结果保证小于2^31
Input
输出两个值，第一个值是没有遮阴路径的最小总长度，第二个是该条路径的总长度，如果没有遮阴路径的最小总长度相等，
Output
输出二者中总路径长度最小的那条路径的长度值。
Sample Input
3 4 1 2 10 2 1 2 11 1 2 3 5 2 2 3 7 1 4 4 1 2 10 2 2 4 10 3 1 3 5 3 3 4 16 2 |
Sample Output
2 18 5 20 |
解题思路：起点为1，终点为n，两个数组，一个存贮路径长度，一个是最少晒到阳光的长度，然后用Dijkstra算法就是~~~~
代码如下：
#include <iostream>
#include <cstring>
const int maxn = ;
const int inf = 0x3f3f3f3f;
using namespace std; int diaA[maxn][maxn], disB[maxn][maxn], n, m, x, y, d1, d2; void init()
{
for (int i = ; i <= n; i++){
for (int j = i; j <= n; j++)
diaA[i][j] = diaA[j][i] = disB[i][j] = disB[j][i] = inf;
}
}
void Dijkstra(){
int dis[maxn], pay[maxn], vis[maxn], i, j, k;
memset(vis, , sizeof(vis));
for (i = ; i <= n; i++){
dis[i] = diaA[][i];
pay[i] = disB[][i];
}
vis[] = ;
for (i = ; i <= n; i++){
int min = inf;
for (j = ; j <= n; j++){
if (!vis[j] && pay[j] < min){
min = pay[j];
k = j;
}
}
vis[k] = ;
for (j = ; j <= n; j++){
if (!vis[j]){
if (pay[k] + disB[k][j]<pay[j] || pay[k] + disB[k][j] == pay[j] && dis[j]>dis[k] + diaA[k][j]){
pay[j] = pay[k] + disB[k][j];
dis[j] = dis[k] + diaA[k][j];
}
}
}
}
cout << pay[n] << ' ' << dis[n] << endl;
} int main(){
while (cin >> n >> m){
init();
for (int i = ; i < m; i++){
cin >> x >> y >> d1 >> d2;
if (d2 < disB[x][y] || d2 == disB[x][y] && d1 < diaA[x][y]){
diaA[x][y] = d1;
disB[x][y] = d2;
}
}
Dijkstra();
}
return ;
}