The Nya graph is an undirected graph with “layers”. Each node in the graph belongs to a layer, there are N nodes in total.
You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.
InputThe first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has three numbers N, M (0 <= N, M <= 10 5) and C(1 <= C <= 10 3), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers l i (1 <= l i <= N), which is the layer of i th node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 10 4), which means there is an extra edge, connecting a pair of node u and v, with cost w.OutputFor test case X, output “Case #X: ” first, then output the minimum cost moving from node 1 to node N.
If there are no solutions, output -1.Sample Input
2 3 3 3 1 3 2 1 2 1 2 3 1 1 3 3 3 3 3 1 3 2 1 2 2 2 3 2 1 3 4
Sample Output
Case #1: 2 Case #2: 3
题意:这个题目好像说的不太清啊,反正就是有n个点,n层楼,相邻楼层之间可以相通,权值为c。还有m条双向边联通点。
题解:问题在于建图,m条边直接连接,然后将楼层看作另外的n个点,将楼层连向楼层上的点,权值为0,将点连向相邻楼层,权值为c。
这里本来要相邻的都有才能连接,但因为是单向边,直接将有点的楼层的点与相邻的连接即可。
要注意连接边的方向要从i->n+v->n+v-1/n+v+1->下一个点,反过来是不行的,可以验证一下。另外如果将点与对应楼层连成双向边,就多余了。
代码:
#include<algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(init,b,c) make_pair(init,make_pair(b,c)) #define rep(i,init,n) for (int i=init;i<=n;i++) #define per(i,init,n) for (int i=n;i>=init;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; const ll mod = 1000000007; ll gcd(ll init, ll b) { return b ? gcd(b, init%b) : init; } const int INF = 0x3f3f3f3f; const int MAXN=200010; struct qnode //优先队列的创建(储存节点v以及到源点的距离C) { int v;//节点v int c;//源点的距离(用来排序) qnode(int _v=0, int _c=0):v(_v),c(_c){} //初始化为0??? bool operator<(const qnode &r)const//定义优先队列的排序方式(实际上可以用pair进行替代),先比较第一维,相等时比较第二维 { return c>r.c;} }; struct Edge//边结构 { int v,cost; //储存边以及权 Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}//初始化??? }; vector<Edge>E[MAXN];//看作二维数组,每个i数组储存着从i边到下一边的所有数据 bool vis[MAXN];//标记数组 int dist[MAXN];//离源点的距离 void Dijkstra(int n, int start) //点的编号从1开始,n是点的个数,start是源点 { memset(vis, false, sizeof(vis));//初始化标记数组 for(int i = 1; i <= n;i++)dist[i] = INF;//初始化距离数组 priority_queue<qnode>que;//创建定义的优先队列,类型为qnote while(!que.empty()) que.pop();//清空队列(这里不明白为什么要清空,是赋了初值吗?那为什么要赋初值) dist[start]=0;//源点到源点的距离初始化为0,以便于得出后续 que.push(qnode(start,0));//源点入队,距离为0 qnode tmp;//qnode类型的中转变量 while(!que.empty()){//只要队列不为空,也可以看作每次出队都是一轮松弛 tmp=que.top();//将队列中d最小的赋给tmp que.pop();//出队 int u = tmp.v;//方便后续的操作,令u=该点的序号 if(vis[u])continue;//如果已被标记,那么跳过 vis[u]=true;//标记 for(int i=0;i<E[u].size();i++){//循环u的下一点的个数次 int v=E[tmp.v][i].v;//v=(点u数组中的下一点) int cost=E[u][i].cost; //cost = (点u数组中到下一点的距离) if(!vis[v]&&dist[v]>dist[u]+cost){ //松弛操作 dist[v]=dist[u]+cost; que.push(qnode(v,dist[v]));//入队 } } } } void addedge(int u,int v,int w){ E[u].push_back(Edge(v,w)); } bool lay[MAXN]; int main(){ int t; int cal=0; scanf("%d", &t); while(t--){ int n,m,c; scanf("%d%d%d", &n,&m,&c); for(int i=1; i<=n*2; i++)E[i].clear(); // memset(lay,false,sizeof(lay)); int v,u; rep(i,1,n){ scanf("%d",&v); // lay[v] = true; if(v>1)addedge(i,v-1+n,c); if(v<n)addedge(i,v+1+n,c); // addedge(i,v+n,0); addedge(v+n,i,0); } // rep(i,1,n-1){ // if(lay[i]&&lay[i+1]){ // addedge(n+i,n+i+1,c); // addedge(n+i+1,n+i,c); // } // } rep(i,1,m){ scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); addedge(v,u,c); } Dijkstra(2*n,1); printf("Case #%d: %d\n", ++cal,dist[n]==INF?-1:dist[n]); } return 0; }