T292306 01最短路 题解

又是一个找不到题目所以自己写的题。。。

40 迪杰斯特拉，但是搞不懂为什么是wa而不是re的

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b);
using namespace std;
int main()
{
	//freopen("9.in","w",stdout);
	srand(time(0));
	int n,m;
	n=10;
	m=10;
	cout<<n<<' '<<m<<endl;
	for1(i,1,m-1)
	{
		int x,y,z;
		x=	1 + (int)n * rand() / (RAND_MAX + 1); 
		y=	1 + (int)n * rand() / (RAND_MAX + 1);
		while(x==y)  y=	1 + (int)n * rand() / (RAND_MAX + 1);
		z=rand()%2;
		cout<<x<<' '<<y<<' '<<z<<endl;
	}
			int x,y,z;
		x=	1;
		y=	1 + (int)n * rand() / (RAND_MAX + 1);
		while(x==y)  y=	1 + (int)n * rand() / (RAND_MAX + 1);
		z=rand()%2;
		cout<<x<<' '<<y<<' '<<z<<endl;
} 

100

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b);
using namespace std;
struct node{
	int w;
	int nex;
	int to;
}a[1000005*3];
int hd[1000005],cnt,ans[1000005];
int n,m,s,t;
bool vis[500005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

void ru(int x,int y,int z)
{
	a[++cnt].to=y;
	a[cnt].w=z;
	a[cnt].nex=hd[x];
	hd[x]=cnt;
}

void bfs()
{
	deque <int > dl;
	for1(i,1,n) ans[i]=1e8;
	ans[s]=0;
	dl.push_front(s);
	while(!dl.empty())
	{
		int x=dl.front();
		dl.pop_front();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=hd[x];i;i=a[i].nex)
		{
			int v=a[i].to;
			if(ans[v]>ans[x]+a[i].w)
			{
				ans[v]=ans[x]+a[i].w;
				if(a[i].w==1) dl.push_back(v);
				else dl.push_front(v);
			}
		}
	}
}
int main()
{
// 	freopen("9.in","r",stdin);
// 	freopen("9.out","w",stdout);
	n=read(),m=read();
	s=1;
	for1(i,1,m)
	{
		int x,y,z;
		x=read(),y=read(),z=read();
		ru(x,y,z);
		ru(y,x,z);
	}
	bfs();
	for1(i,1,n) 
	if(ans[i]==1e8) printf("%d ",-1);
	else printf("%d ",ans[i]);
}