//#include<iostream>
//#include<string>
//#include<cmath>
//#include<ctype.h>
//#include<memory.h>
//#include<string.h>
//#include<algorithm>
//#include<map>
//#include<iomanip>
//#include<set>
//#include<list>
//#include<vector>
//#include<stack>
//#include<queue>
//using namespace std;
//const int maxn = 500500;
//const int INF = 0x3f3f3f;
//
//int n, m, c;//n节点数 m额外边数 c跨层代价
//
//vector<pair<int, int> >edge[maxn];//edge[i] i=u; pair.first=v; pair.second=w;
//int dis[maxn];
//
//int dijkstra()
//{
// memset(dis, INF, sizeof(dis));
// priority_queue<pair<int, int> >q;
// q.push(make_pair(0, 1));
// dis[1] = 0;
// while (!q.empty())
// {//cout << 123 << endl;
// int u = q.top().second;
// q.pop();
//
// for (int i = 0; i < edge[u].size(); i++)
// {
// int v = edge[u][i].first;
// int w = edge[u][i].second;
// if (dis[v] > dis[u] + w)
// {
// dis[v] = dis[u] + w;
// q.push(make_pair(-dis[v], v));
// }
// }
// }
// return dis[n];
//}
//
//int main()
//{
// int Cnt = 0;
// int T;
// //cin >> T;
// scanf("%d", &T);
// while (T--)
// {
// //cin >> n >> m >> c;
// scanf("%d%d%d", &n, &m, &c);
// for (int i = 0; i <= 3 * n; i++)
// edge[i].clear();
//
// for (int i = 1; i <= n; i++)//读入n个点所在的层
// {
// int layer;
// //cin >> layer;
// scanf("%d", &layer);
// edge[2 * layer + n - 1].push_back(make_pair(i, 0));//layer*2+n-1 = layer层的入点
// edge[i].push_back(make_pair(layer * 2 + n, 0));//layer*2+n = layer层的出点
// }
//
// for (int i = 0; i < m; i++)
// {
// int u, v, w;
// //cin >> u >> v >> w;
// scanf("%d%d%d", &u, &v, &w);
// edge[u].push_back(make_pair(v, w));
// edge[v].push_back(make_pair(u, w));
// }
//
// for (int i = 1; i <= n; i++)
// {
// int u = 2 * i + n;
// if (i > 1)
// {
// int v = u - 3;//u->v = c 上一层到该层
// edge[u].push_back(make_pair(v, c));
// }
// if (i < n)
// {
// int v = u + 1;//u->v = c 该层到下一层
// edge[u].push_back(make_pair(v, c));
// }
// }
// int ans = dijkstra();
// cout << "Case #" << ++Cnt << ": ";
// if (ans == INF)
// cout << -1 << endl;
// else
// cout << ans << endl;
// }
// return 0;
//}
//
/*
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
*/
#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100100;
int dis[3 * maxn];
bool vis[3 * maxn];
struct edge
{
int v, w;
edge(int v, int w) :v(v), w(w) {}
};
struct node
{
int u, w;
node()
{}
node(int u, int w) :u(u), w(w) {}
bool operator <(const node& a)const
{
return w > a.w;
}
};
vector<edge> g[3 * maxn];//使用3*N是考虑了可能添加的结点
vector<int> layer[maxn];//layer[i]存储在第i层的结点
void dijkstra(int s)
{
memset(dis, INF, sizeof(dis));
memset(vis, 0, sizeof(vis));
priority_queue<node> q;
dis[s] = 0;
q.push(node(s, 0));
while (!q.empty())
{
node f = q.top();
q.pop();
int u = f.u;
if (!vis[u])
{
vis[u] = 1;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].v;//u为起点的所有边 到达的点
if (!vis[v] && dis[v] > dis[u] + g[u][i].w)
{
dis[v] = dis[u] + g[u][i].w;
q.push(node(v, dis[v]));
}
}
}
}
}
int main()
{
int t, n, m, c;
int u, v, w, l;
//cin >> t;
scanf("%d", &t);
for (int k = 1; k <= t; k++)
{
//cin >> n >> m >> c;
scanf("%d%d%d", &n, &m, &c);
for (int i = 0; i <= n; i++) layer[i].clear();
for (int i = 0; i <= 3 * n; i++) g[i].clear();//2n表示上次操作可能添加了2*n个结点
//n个点为i到i+1层，n个点为i到i-1层
for (int i = 1; i <= n; i++)//n 个点 所在层的信息存在layer
{
//cin >> l;
scanf("%d", &l);//第i个点 在 l 层
layer[l].push_back(i);
}
for (int i = 1; i <= m; i++)//m 条 边 及其 权重存在g中
{
//cin >> u >> v >> w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(edge(v, w));
g[v].push_back(edge(u, w));
}
int addnode = n + 1;//新添加的点的编号
//按层数递增的顺序实现i能访问i+1层:使用一个结点进行沟通
for (int i = 1; i < n; i++)
{
if (!layer[i].empty() && !layer[i + 1].empty())//如果第i层和第i+1层有结点
{
//第i层的各个结点到添加结点node的距离为c,结点node到第i+1层的结点的距离为0
//这样就实现了第i层结点访问第i+1层结点的距离为c
for (int j = 0; j < layer[i].size(); j++)
{
int u = layer[i][j];
g[u].push_back(edge(addnode, c));
}
for (int j = 0; j < layer[i + 1].size(); j++)
{
int v = layer[i + 1][j];
g[addnode].push_back(edge(v, 0));
}
addnode++;
}
}
//按层数递减的顺序实现i访问i-1层:使用一个结点进行沟通
for (int i = n; i > 1; i--)
{
if (!layer[i].empty() && !layer[i - 1].empty())//如果第i层和第i-1层有结点
{
//第i层的各个结点到添加结点node的距离为c,结点node到第i-1层的结点的距离为0
//这样就实现了第i层结点到第i-1层结点的距离为c
for (int j = 0; j < layer[i].size(); j++)
{
int u = layer[i][j];
g[u].push_back(edge(addnode, c));
}
for (int j = 0; j < layer[i - 1].size(); j++)
{
int v = layer[i - 1][j];
g[addnode].push_back(edge(v, 0));
}
addnode++;
}
}
dijkstra(1);
cout << "Case #" << k << ": ";
if (dis[n] == INF)
cout << -1 << endl;
else
cout << dis[n] << endl;
/*printf("Case #%d: ", t);
if (dis[n] == INF)
printf("-1\n");
else
printf("%d\n", dis[n]);*/
}
return 0;
}
转载：https://blog.csdn.net/weixin_41894030/article/details/101036580
查看评论