班级建设怎样建立班级网站,wordpress 评论 html,wordpress怎么修改数据库密码忘记,岳阳网站开发一、心路历程
这一个题目写了三天#xff0c;可以说是非常挣扎了#xff0c;明明是例题#xff0c;但是就是倔强着不去看书上的题解#xff0c;WA了7次#xff0c;TLE了4次。 写了不知道多少条测试用例#xff0c;一遍一遍的过#xff0c;一点一点的调试。 最后终于找到…一、心路历程
这一个题目写了三天可以说是非常挣扎了明明是例题但是就是倔强着不去看书上的题解WA了7次TLE了4次。 写了不知道多少条测试用例一遍一遍的过一点一点的调试。 最后终于找到了规则
二、思路
1、题目要求1到N必须按照顺序排那么我们就可以认为 对每个 i 1存在 i -1 到 i 的 0 的斥力
2、我们每一条A到B的排斥力P看作B到A引力力 P * (-1)
3、规则1中 斥力和 输入的斥力都按照第二条规则转化引力然后不考虑斥力
4、用 BellmanFord算法对转换成的和输入的引力集合判断是否存在负圈存在直接输出-1
5、不存在负圈则直接对转换成的和输入的引力集合使用dijkstra算法起点是1如果d[N]大于1000000007每条边最大值乘以边数加7是为了防止边界出错)则输出-2否则输出d[N]。
三、代码
#include iostream
#include vector
#include queue
using namespace std;
struct Node
{int from, to, cost;Node(int from 0, int to 0, int cost 0) : from(from), to(to), cost(cost) {}
};
vectorNode nodes;
typedef pairint, int P;
vectorP edges[1007];
int d[1007], N, inf 0x3f3f3f3f, ML, MD, area[1007][1007];
bool used[1007];
void input()
{int from, to, cost;for (int i 1; i ML; i){scanf(%d%d%d, from, to, cost);edges[from].push_back(P(cost, to));nodes.push_back(Node(from, to, cost));}for (int i 1; i MD; i){scanf(%d%d%d, from, to, cost);edges[to].push_back(P(-cost, from));nodes.push_back(Node(to, from, -cost));}for (int i 2; i N; i){edges[i].push_back(P(0, i - 1));nodes.push_back(Node(i, i - 1, -1));}
}
bool bellmanFord(int s)
{bool flag false;for (int i 1; i N; i){d[i] inf;}d[s] 0;for (int i 1; i N; i){for (int j 0; j nodes.size(); j){if (d[nodes[j].from] nodes[j].cost d[nodes[j].to]){d[nodes[j].to] d[nodes[j].from] nodes[j].cost;if (i N){flag true;}}}}return flag;
}
void dijkstra(int s)
{for (int i 1; i N; i){d[i] inf;used[i] false;}d[s] 0;priority_queueP, vectorP, greaterP que;que.push(P(0, s));while (!que.empty()){P current que.top();que.pop();if (used[current.second] || current.first d[current.second]){continue;}for (int i 0; i edges[current.second].size(); i){P toEdge edges[current.second][i];if (d[current.second] toEdge.first d[toEdge.second]){d[toEdge.second] toEdge.first d[current.second];que.push(P(d[toEdge.second], toEdge.second));}}}
}
void solve()
{if (bellmanFord(1)){printf(%d\n, -1);}else{dijkstra(1);if (d[N] 1000000007){printf(%d\n, -2);}else{printf(%d\n, d[N]);}}
}
int main()
{scanf(%d%d%d, N, ML, MD);input();solve();return 0;
}
