2019BNUZ校内赛现场赛A.Level Up【最短路】

题目大意

给你n个点(n<=1000),m条有向边，求点a到点b的最短路，如果没有输出-1.
这里面有一个条件，你可以将m条边中任意一条边的权值整除2

题解

比赛的时候，一直没想到如何优化，比赛完之后，大佬对我说，这么简单的最短路都不会，QAQ…, 然后跟我说了一下思路，问我最短路堆优化是不是每一次都要往优先队列里面塞一个点，那就在塞的过程中，对这个点做一下标记就好了，想了一下午，才想出来，QAQ，感觉就跟DP差不多的原理，真的很菜，直接把kuangbin版 Dijkstra+堆优化改一改就好了，太菜了

AC_code:

/*
* 使用优先队列优化 Dijkstra 算法
* 复杂度 O(ElogE)
* 注意对 vector<Edge>E[MAXN] 进行初始化后加边
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;


const ll INF=1000000005LL;
const int MAXN=1005;
struct qnode {
	int v;
	ll c;
	int flag;// 1表示已经使用了技能卡  0表示没有
	qnode(int _v=0,ll _c=0,int _flag=0):v(_v),c(_c),flag(_flag) {}
	bool operator <(const qnode &r)const {
		return c>r.c;
	}
};
struct Edge {
	int v;
	ll cost;
	Edge(int _v=0,ll _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
bool vis[2][MAXN];// 1表示已经使用了技能卡  0表示没有
ll dist[2][MAXN];// 1表示已经使用了技能卡  0表示没有
//点的编号从 1 开始
void Dijkstra(int n,int start) {
	memset(vis,false,sizeof(vis));
	for(int i=1; i<=n; i++)dist[0][i]=dist[1][i]=INF;
	priority_queue<qnode>que;
	while(!que.empty())que.pop();
	dist[0][start]=dist[1][start]=0;
	que.push(qnode(start,0,0));
	qnode tmp;
	while(!que.empty()) {
		tmp=que.top();
		que.pop();
		int u=tmp.v;
		int flag=tmp.flag;
		if(vis[flag][u])continue;
		vis[flag][u]=true;
		int len=E[u].size();
		for(int i=0; i<len; i++) {
			int v=E[u][i].v;
			ll cost=E[u][i].cost;
			if(!vis[flag][v]&&dist[flag][v]>dist[flag][u]+cost) {
				dist[flag][v]=dist[flag][u]+cost;
				que.push(qnode(v,dist[flag][v], flag));
			}
			if(!vis[1][v]&&dist[1][v]>dist[0][u]+cost/2&&!flag) {
				dist[1][v]=dist[0][u]+cost/2;
				que.push(qnode(v,dist[1][v], 1));
			}
		}
	}
}
void addedge(int u,int v,ll w) {
	E[u].push_back(Edge(v,w));
}
int main() {
	int t, cas = 1;
	scanf("%d", &t);
	while(t--) {
		printf("Case #%d:\n",cas++);
		int n, m;
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; i++) {
			E[i].clear();
		}
		ll ans = 0;
		int a, b;
		ll c;
		while(m--) {
			scanf("%d %d %lld", &a, &b, &c);
			addedge(a, b, c);
		}
		int x, y;
		scanf("%d %d", &x, &y);
		Dijkstra(n, x);
		ans = min(dist[0][y],dist[1][y]);
		if(ans == INF) {
			printf("-1\n");
		} else
			printf("%lld\n", ans);
	}
	return 0;
}