网站建设首先,lol视频网站模板,网站空间双线空间是什么意思,汽车网站策划书追债之旅
思路
最短路问题#xff0c;考虑DijkstraDijkstraDijkstra#xff0c;用一个二维dis[i][j]dis[i][j]dis[i][j]数组#xff0c;表示第iii天到达jjj号点的最小花费#xff0c;disdisdis数组的更新方式改为if(dis[day][to]dis[day−1][now]value[to]cost[day])…追债之旅
思路
最短路问题考虑DijkstraDijkstraDijkstra用一个二维dis[i][j]dis[i][j]dis[i][j]数组表示第iii天到达jjj号点的最小花费disdisdis数组的更新方式改为if(dis[day][to]dis[day−1][now]value[to]cost[day])if(dis[day][to] dis[day - 1][now] value[to] cost[day])if(dis[day][to]dis[day−1][now]value[to]cost[day])则更新disdisdis数组所以我们最后只要遍历iii天到达nnn号节点也就是dis[i][n]dis[i][n]dis[i][n]数组最后取其最小值就行。
DijkstraDijkstraDijkstra的关键就是一个有能够记录day,value,posday, value, posday,value,pos当前天数这个状态的最小值当前位置这样的结构体然后重载一下小于号运算符就可以跑个DijkstraDijkstraDijkstra板子了。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \n
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll x 0, f 1; char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return x * f;
}const int N1 1e3 10, N2 2e4 10;int head[N1], to[N2], nex[N2], value[N2], cnt 1;
int visit[20][N1], dis[20][N1], cost[20], n, m, k;struct Node {int day, pos, value;Node(int _day 0, int _pos 0, int _value 0) : day(_day), pos(_pos), value(_value) {}bool operator (const Node t) const {return value t.value;}
};void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void Dijkstra() {for(int i 0; i k; i)for(int j 0; j n; j)dis[i][j] inf;priority_queueNode q;q.push(Node(0, 1, 0));dis[0][1] 0;while(!q.empty()) {Node temp q.top();q.pop();if(visit[temp.day][temp.pos]) continue;visit[temp.day][temp.pos];int u temp.pos, day temp.day, w temp.value;for(int i head[u]; i; i nex[i]) {if(day 1 k) continue;if(dis[day 1][to[i]] w value[i] cost[day 1]) {dis[day 1][to[i]] w value[i] cost[day 1];q.push(Node(day 1, to[i], dis[day 1][to[i]]));}}}
}int main () {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n read(), m read(), k read();for(int i 1; i m; i) {int x read(), y read(), w read();add(x, y, w);add(y, x, w);}for(int i 1; i k; i)cost[i] read();Dijkstra();int ans inf;for(int i 1; i k; i)ans min(ans, dis[i][n]);printf(%d\n, ans inf ? -1 : ans);return 0;
}
