POJ 1724 ROADS

題目：
    總共N個點，給定R條道路，每條共有S,D,L,T代表S點到D點這條路長度L且須花費T元，題目求從1為起點，N為終點，在花費<=K元的情況下走到終點的最短距離。
    注意同一個S到D可能有多條道路。
想法：
    用Dis[i][j]表示"從起點1走到i點花費j元的最短距離"，所以做SPFA的時候，每次就去更新Dis[i][0~K]的值，使其值盡可能的小，最後再去檢查Dis[N][0~K]的最小值是多少。
    因為S到D可能有多條道路，所以用vector來存較為簡單。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	#define INF 99999999
	struct Point_type {
	vector<int> D; // next point index
	vector<int> L; // length
	vector<int> T; // toll
	}S[101];
	int Dis[101][10001]; //Dis[i][j] 為從起點1到點i花費j元的最短距離
	int main()
	{
	int K, N, R;
	scanf("%d %d %d", &K, &N, &R);
	// Initialize Dis[][]
	for (int i = 1; i <= N; ++i)
	for (int j = 0; j <= K; ++j)
	Dis[i][j] = INF;
	for (int i = 0; i <= K; ++i)
	Dis[1][i] = 0;
	// Input
	int s, d, l, t;
	for (int i = 0; i < R; ++i) {
	scanf("%d %d %d %d", &s, &d, &l, &t);
	S[s].D.push_back(d);
	S[s].L.push_back(l);
	S[s].T.push_back(t);
	}
	// SPFA
	queue<int> Q;
	bool inQueue[101] = {0};
	Q.push(1);
	inQueue[1] = true;
	while (!Q.empty()) {
	int now = Q.front();
	inQueue[now] = false;
	Q.pop();
	for (int i = 0; i < S[now].D.size(); ++i) {
	int nxt = (S[now].D)[i];
	int L = S[now].L[i];
	int T = S[now].T[i];
	for (int j = 0; j + T <= K; ++j) {
	if (Dis[now][j] + L < Dis[nxt][j+T]) {
	Dis[nxt][j+T] = Dis[now][j] + L;
	if (!inQueue[nxt]) {
	Q.push(nxt);
	inQueue[nxt] = true;
	}
	}
	}
	}
	}
	// Analysis
	int Shortest = INF;
	for (int i = 0; i <= K; ++i)
	if (Dis[N][i] < Shortest)
	Shortest = Dis[N][i];
	// Output
	if (Shortest == INF) puts("-1");
	else printf("%d\n", Shortest);
	}

view raw [POJ] 1724 ROADS.cpp hosted with ❤ by GitHub