大连网站建设信息,专业的网站建设,网站建设流量什么意思,网站建设合同免费下载我写了好多注释#xff0c;一看就能看懂#xff0c;这个题目我想了6#xff0c;7个小时#xff0c;一开始忽略了船的位置和要把船安置的位置一致的情况#xff0c;补上就对了。
#include iostream
using namespace std;
int inf 0x3f3f3f3f, num[1007], dp[1007…我写了好多注释一看就能看懂这个题目我想了67个小时一开始忽略了船的位置和要把船安置的位置一致的情况补上就对了。
#include iostream
using namespace std;
int inf 0x3f3f3f3f, num[1007], dp[1007][207], L[207][207], S[207][207], N, M, R;
void init()
{for (int i 1; i N; i){for (int j 1; j N; j){L[i][j] inf;S[i][j] inf;}L[i][i] 0;S[i][i] 0;}
}
void input()
{int from, to, cost;char op;for (int i 1; i M; i){scanf(%d %d %d %c\n, from, to, cost, op);if (op S){if (cost S[from][to]){S[from][to] cost;}if (cost S[to][from]){S[to][from] cost;}}else if (op L){if (cost L[from][to]){L[from][to] cost;}if (cost L[to][from]){L[to][from] cost;}}}scanf(%d, R);for (int i 1; i R; i){scanf(%d, num[i]);}
}
void floyd()
{for (int k 1; k N; k){for (int i 1; i N; i){for (int j 1; j N; j){if (L[i][k] ! inf L[k][j] ! inf){if (L[i][k] L[k][j] L[i][j]){L[i][j] L[i][k] L[k][j];}}if (S[i][k] ! inf S[k][j] ! inf){if (S[i][k] S[k][j] S[i][j]){S[i][j] S[i][k] S[k][j];}}}}}
}
void handleNormalLine(int i, int j)
{// dp[i][j]是从num[1]到达num[i]并且到达num[i]时船在j的最小路径当i大于1时dp[i][j]一定与num[i-2]走到num[i-1]时停船的位置有关// 我们需要从num[i-1]走陆路到k然后走水路到j把船停在j之后走陆路从j到num[i]dp[i][j] inf;for (int k 1; k N; k){if (k ! j){// 从num[i-1]到k的陆路不通从k到j的水路不通从j到num[i]的陆路不通从1到num[i-1]并且停船到k实现不了,那么这种情况不用计算if (L[num[i - 1]][k] inf || S[k][j] inf || L[j][num[i]] inf || dp[i - 1][k] inf){continue;}if (L[num[i - 1]][k] S[k][j] L[j][num[i]] dp[i - 1][k] dp[i][j]){dp[i][j] L[num[i - 1]][k] S[k][j] L[j][num[i]] dp[i - 1][k];}}else{// k和j相等时就不需要走陆路到k然后再走水路到j了直接从num[i-1]走陆路到num[i]即可因为jk船已经在j了不用管船if (L[num[i - 1]][num[i]] inf || dp[i - 1][k] inf){continue;}if (L[num[i - 1]][num[i]] dp[i - 1][k] dp[i][j]){dp[i][j] L[num[i - 1]][num[i]] dp[i - 1][k];}}}
}
void handleFirstLine(int i, int j)
{// i1时船就在num[i]dp[i][j] i1 代表开船到j船放在j然后陆路走回来num[i]// 走水路开船从num[i]到j然后船停在j之后从j走陆路回到num[i]如果num[i]到j的水路或者j到num[i]的陆路不通那么这个都无法实现if (S[num[i]][j] inf || L[j][num[i]] inf){dp[i][j] inf;return;}dp[i][j] S[num[i]][j] L[j][num[i]];
}
void doDp()
{// 我们用dp[i][j] 代表邮递员从 num[1]按照顺序一个个走到num[i]即达到邮递员在num[i]且船的位置在j的状态下最小的消耗for (int i 1; i R; i){for (int j 1; j N; j){if (i 1){handleFirstLine(i, j);}else{handleNormalLine(i, j);}}}
}
int findAns()
{int ans inf;for (int i 1; i N; i){if (dp[R][i] ans){ans dp[R][i];}}return ans;
}
int main()
{while (true){scanf(%d%d, N, M);if (N 0 M 0){break;}init();input();floyd();doDp();printf(%d\n, findAns());}return 0;
}
