最短路径(邻接矩阵)

题目连接
题意：按照要求课求出矩阵c[i][j] i到j的距离
然后所求答案为
ans=min(dis[0][j]%m);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e6+5;
ll x[N],y[N];
ll c[1005][1005];
ll z[N];
ll dis[N];
//dij算法
void dij(int n)
{
	priority_queue< pii,vector<pii> ,greater<pii> > que;//默认优先是从大到小，按第一关键字排序，这样是从小到大排序
	memset(dis,0x3f3f3f,sizeof(dis));
	que.push(mp(0,0));
	while(!que.empty())
	{
		pii p=que.top();
		que.pop();
		int u=p.se;
		for(int i=0;i<n;i++)
		{
			if(i==u) continue;
			if(dis[i]>p.fi+c[u][i]) 
			{
				dis[i]=p.fi+c[u][i];que.push(mp(dis[i],i));
			}
		}
	}
} 
/*
//这种写法耗时大
void dij(int n){
    priority_queue<pii,vector<pii>, greater<pii> >q;
    q.push(pii(0,0));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    pii u,v;dis[0]=0;
    while(!q.empty()){
        u=q.top();q.pop();
        if(u.first>dis[u.second])continue;
        else dis[u.second]=u.first;
        for(int i=0;i<n;i++){
            if(i==u.second )continue;
            v.second=i;
            v.first=u.first+c[u.second][i];
            q.push(v);
        }
    }
}
*/
int main()
{
	int n,m,i,j,k;
	while(scanf("%d%d%lld%lld%lld%lld",&n,&m,&x[0],&x[1],&y[0],&y[1])!=EOF)
	{
		for(i=0;i<n*n;i++)
		{
			if(i>1)
			{
				x[i]=(12345+x[i-1]*23456%5837501+x[i-2]*34567%5837501+x[i-1]*x[i-2]%5837501*45678)%5837501;
				y[i]=(56789+y[i-1]*67890%9860381+y[i-2]*78901%9860381+y[i-1]*y[i-2]%9860381*89012)%9860381;
			}
			z[i]=(x[i]*90123+y[i])%8475871+1;
		}
		int t=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++) 
			{
				if(i==j) c[i][j]=0; 
				else c[i][j]=z[t];
				t++;
			}
		dij(n);
		ll ans=12345678;
		for(i=1;i<n;i++)
			ans=min(ans,dis[i]%m);
		printf("%lld
",ans);
	} 
}
最短路径(邻接矩阵)

结果比较：
