记录编号	590505	评测结果	RRRRRRRRRR
题目名称	[USACO Oct08] 轮子的旋转	最终得分	0
用户昵称	dream	是否通过	未通过
代码语言	C++	运行时间	0.031 s
提交时间	2024-07-10 12:31:44	内存使用	3.42 MiB

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PI;
const int N=10005,M=50005*2;
int hd[N],val[M],to[M],nxt[M],mk[N],dis[N];
int n,m,k,s,t;
int cnt;
void add(int x,int y,int v){
	cnt++;
	val[cnt]=v;
	to[cnt]=y;
	nxt[cnt]=hd[x];
	hd[x]=cnt;
}
int dijkstra(){
	memset(mk,0,sizeof(mk));
	memset(dis,0x3f,sizeof(dis));
	priority_queue<PI,vector<PI>,greater<PI>> q;
	q.push({0,s});
	dis[s]=0;
	while(q.size()){
		PI t=q.top();
		q.pop();
		if(mk[t.second]){
			continue;
		}
		mk[t.second]=0;
		for(int i=hd[t.second];i;i=nxt[i]){
			int y=to[i];
			if(dis[y]>dis[t.second]+val[i]){
				dis[y]=dis[t.second]+val[i];
				q.push({dis[y],y});
			}
		}
	}
	return dis[t];
}
int main(){
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
	cin>>n>>m>>k;
	cin>>s>>t;
	for(int i=0;i<m;i++){
		int x,y,v;
		cin>>x>>y>>v;
		add(x,y,v);
		add(y,x,v);
	}
	if(k==0){
		cout<<dijkstra();
	}
	else if(k==1){
		int res=2147483647;
		for(int i=1;i<=m*2;i++){
			int t=val[i];
			val[i]=0;
			res=min(res,dijkstra());
			val[i]=t;
		}
		cout<<res;
	}
	return 0;
}