C语言BFS(5)___TT与魔法师(swust oj 2464)

2
4 3
1 2 1 1
2 3 2 2
3 4 3 3 
4 3
1 2 1 1
2 3 2 2
3 4 3 2

6 
-1

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <stdlib.h>
using namespace std;
int memory[1001][1001][4],n,m;
int mpt[1001][1001][4],money[1001][1001][4];
bool book[1001][1001][4]; 
vector<int>way[1001]; 
int Min(int a,int b){
	return (a>b)? b:a;
}
int dfs(int pre,int step,int k){
	
	if(step==n)return 0;
	if(memory[pre][step][k])return memory[pre][step][k];
	book[pre][step][k]=true;
	int i,ans=999999999;
	for(i=0;i<way[step].size();i++){
		//cout<<step<<"→"<< way[step][i]<<endl;
		//printf("book[%d][%d]=%d\n",way[step][i],k%3+1,book[way[step][i]][k%3+1]);
		if(mpt[step][way[step][i]][k]==0 || book[step][way[step][i]][k%3+1]==true)continue;
		//cout<<step<<"→"<< way[step][i]<<" K:"<<k<<endl;
		ans=Min(ans,dfs(step,way[step][i],k%3+1)+money[step][way[step][i]][k]);
	}
	book[pre][step][k]=false;
	//printf("memort[%d][%d]=%d\n",step,k,ans); 
	if(ans!=999999999) 
	memory[pre][step][k]=ans;
	return ans;
} 
void init(){
	int i;
	for(i=0;i<1001;i++) way[i].clear();
	memset(memory,0,sizeof(memory));
	memset(money,0,sizeof(money));
	memset(mpt,0,sizeof(mpt)); 
	memset(book,0,sizeof(book));
}
int main()
{
	int i,j,v,u,k,w,t,ans;
	cin>>t;
	while(t--){
		cin>>n>>m;
		init();
		for(i=0;i<m;i++){
			scanf("%d%d%d%d",&v,&u,&w,&k);
			if(mpt[v][u][1]==0 && mpt[v][u][2]==0 && mpt[v][u][3]==0){
			way[v].push_back(u);
			way[u].push_back(v);
			}
			if(money[v][u][k]==0) money[v][u][k]=w,money[u][v][k]=w;
			else{
				money[v][u][k]=Min(money[v][u][k],w);
				money[u][v][k]=Min(money[u][v][k],w);
			}
			mpt[u][v][k]=mpt[v][u][k]=1; 
		}
		ans=dfs(0,1,1);
		if(ans!=999999999)printf("%d\n",ans);
		else printf("-1\n");

	} 
	return 0; 
 } 

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <stdlib.h>
using namespace std;
struct node
{
	int data,v,w;
};
struct node1
{
	int step,v;
};
int n,m;
int visit[1001][4],dis[1001][4];  //visit数组是记录当前状态 [节点编号][通行证编号]是否在队列中.
vector<node>mpt[1001];
void SPFA()
{
	node1 s,e;
	int i,j,ss;
	queue<node1>team;
	s.step=1;s.v=1;
	team.push(s);
	visit[1][1]=1;
	while(team.size()){   //用队列中的状态去更新最小花费.
		s=team.front();
		team.pop();
		visit[s.step][s.v]=0;
		ss=mpt[s.step].size();
		for(i=0;i<ss;i++){
			if(mpt[s.step][i].v!=s.v)continue;
			if(dis[s.step][s.v]+mpt[s.step][i].w>=dis[mpt[s.step][i].data][s.v%3+1])continue; 
			dis[mpt[s.step][i].data][s.v%3+1]=dis[s.step][s.v]+mpt[s.step][i].w;  //松弛
			if(visit[mpt[s.step][i].data][s.v%3+1]!=0)continue;
			e.step=mpt[s.step][i].data;
			e.v=s.v%3+1;
			visit[e.step][e.v]=1;
			team.push(e);
		}
	}
	int min=1999999999;
	for(i=1;i<4;i++)if(min>dis[n][i])min=dis[n][i];
	if(min!=1999999999)cout<<min<<endl;
	else cout<<"-1"<<endl;
 } 
int main()
{
	int i,j,t,x,y;
	cin>>t;
	while(t--){
		cin>>n>>m;
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)for(j=0;j<4;j++)dis[i][j]=1999999999;
		dis[1][1]=0;
		for(i=0;i<1001;i++)mpt[i].clear(); 
		for(i=0;i<m;i++){
			node s;
			cin>>x>>y>>s.w>>s.v;
			s.data=x;
			mpt[y].push_back(s);
			s.data=y;
			mpt[x].push_back(s);
		}
		SPFA();
	}
	return 0;
}