C++ 解法, 执行用时: 1ms, 内存消耗: 248KB, 提交时间: 2017-06-11

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

#define INF 2000
struct Node{
	int x, y;
	int k;
	Node() {
		k = INF;
	}
};
int main() {
	int N, M,result;
	while (cin >> N >> M) {		
		vector<vector<Node>> map(N+1, vector<Node>(N+1));

		for (int i = 0;i < M;i++) {
			int p, q, k, x, y;
			cin >> p >> q >> k >> x >> y;
			map[p][q].x = x;
			map[p][q].y = y;
			map[p][q].k = k;
			map[q][p] = map[p][q];
		}

		vector<int> visted(N + 1,0), cost(N + 1,INF);
		for (int i = 1;i < N + 1;i++) {
			if (map[1][i].k != INF) {
				if (map[1][i].k < map[1][i].x)
					cost[i] = map[1][i].k;
				else
					cost[i] = map[1][i].y + map[1][i].k;
			}
		}
		cost[1] = 0;

		for (int i = 2;i < N+1;i++) {
            
			int min = INF,pos;
			for (int j = 1;j < N + 1;j++) {
				if (visted[j] == 0 && cost[j] < min) {
					min = cost[j];
					pos = j;
				}
			}

			visted[pos] = 1;

			for (int j = 1;j < N + 1;j++) {
				if (visted[j] == 0) {
					int temp;
					if (((map[pos][j].k + cost[pos]) < map[pos][j].x) || (cost[pos] + 1 > map[pos][j].y))
						temp = cost[pos] + map[pos][j].k;
					else
						temp = map[pos][j].y + map[pos][j].k;
					if (temp < cost[j]) {
						cost[j] = temp;
					}
				}
			}
		}

		cout << cost[N] + 1 << endl;

	}
	return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2017-06-24

#include<stdio.h>
#include<vector>
using namespace std;
#define INF 1005
struct route{
    int x,y;
    int k; //routes[i][j] 表示从i港口到j港口需要k天，其中第x到第y天禁止通行
    route(){
        k = INF;
    }
};
int dijstra(int n, vector<vector<route>> &routes){
    vector<int> time(n+1, INF);  //time[i] 表示从1号港口到i号港口需要几天
    for(int i = 1; i <= n; i++){
        if(routes[1][i].k != INF){
            if(routes[1][i].k < routes[1][i].x){
                time[i] = routes[1][i].k;                               //初始化time数组
            }
            else time[i] = routes[1][i].y + routes[1][i].k;
        }
    }
    routes[1][1].k = 1;
    for(int p = 1; p <= n; p++){                           
        int min = INF;
        int j = -1;
        for(int i = 1; i <= n; i++){
            if(routes[i][i].k != 1 && time[i] < min){
                min = time[i];
                j = i;
            }
        }
        if(j == -1) break;
        else{
            routes[j][j].k = 1;
            for(int i = 1; i <= n; i++){
                if(routes[i][i].k != 1){
                    int temp;
                    if(routes[j][i].k+time[j] < routes[j][i].x || time[j] >= routes[j][i].y){        
                                                //行程中没有遇到恶劣天气
                        temp = time[j] + routes[j][i].k;
                    }
                    else temp =routes[j][i].y + routes[j][i].k;
                    if(temp < time[i]) time[i] = temp;
                }
            }
        }
    }
    return time[n]+1;
}
int main(){
    int n, m,p,q,k,x,y;
    scanf("%d%d", &n,&m);
    vector<vector<route>> routes(n+1, vector<route>(n+1));
    for(int i = 0; i < m; i++){
        scanf("%d%d%d%d%d", &p, &q, &k, &x, &y);
        routes[p][q].k = k;
        routes[p][q].x = x;
        routes[p][q].y = y;
        routes[q][p] = routes[p][q];
    }
    printf("%d\n", dijstra(n, routes));
}