放些模板

懒得去找……
而且我也比较熟悉 😀


1.乘法逆元(包括扩展gcd)—对应zoj3609

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#define ls id<<1
#define rs id<<1|1
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int egcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return a;}
	int ret=egcd(b,a%b,x,y);
	int tmp=x;x=y;y=tmp-(a/b)*y;
	return ret;
}
int calni(int a,int m){
	int x,y,g=egcd(a,m,x,y);
	if(1%g!=0)return -1;
	x*=1/g;m=abs(m);
	int ret=x%m;if(ret<=0)ret+=m;
	return ret;
}
int main(){
	int T;read(T);
	while(T--){
		int a,m;
		read(a),read(m);
		int ni=calni(a,m);
		if(ni==-1){printf("Not Exist\n");continue;}
		printf("%d\n",ni);
	}
	return 0;
}

2.Dijkstra(无堆优化)(%%%passer)

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN=500033;
const int INF=2147483647;
struct Edge{
	int nx,to,val;
	Edge(){}
	Edge(int n,int t,int v):nx(n),to(t),val(v){}
}E[MAXN];
int first[10033],ecnt=1;
inline void addedge(int f,int t,int v)
{
	E[++ecnt]=Edge(first[f],t,v);first[f]=ecnt;
}
int n,m,s;
int dist[10033];
bool vis[10033];
void dijskra()
{
	for(int i=1;i<=n;i++)
		dist[i]=INF;
	dist[s]=0;
	int k;
	while(true)
	{
		k=-1;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&(k==-1||dist[i]<dist[k])) k=i;
		if(k==-1) break;
		vis[k]=1;
		for(int i=first[k];i;i=E[i].nx)
		{
			dist[E[i].to]=min((ll)dist[E[i].to],(ll)dist[k]+E[i].val);
		}
	}
}
int main()
{
	int f,t,v;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&f,&t,&v);
		addedge(f,t,v);
	}
	dijskra();
	for(int i=1;i<=n;i++)
	{
		printf("%d ",dist[i]);
	}
	return 0;
}

 

放些模板》上有1个想法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注