turn init d+ cmp push typedef for jks make
一,求逆元 - 费马小定理
二,树状数组
//amodm
#include < cstdio > #include < cstring > #include < iostream > using namespace std;
typedef long long lol;
int n,
p;
lol qpow(lol x) {
int y = p - 2;
lol ans = 1;
while (y) {
if (y & 1) ans *= x,
ans %= p;
x *= x;
x %= p;
y /= 2;
}
return ans;
}
inline void write(lol x) {
if (x < 0) putchar(' - '),
x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int main() {
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++) {
write(qpow(i) % p);
putchar('\n');
}
return 0;
}
三,最大流 - Dinic
//BIT
#include < cstdio > #include < cstring > #include < iostream > using namespace std;
typedef long long lol;
lol n,
m;
lol f[500010];
lol lowbit(lol x) {
return x & -x;
}
void add(lol x, lol k) {
for (int i = x; i <= n; i += lowbit(i)) f[i] += k;
}
lol getsum(lol x) {
lol ans = 0;
for (int i = x; i; i -= lowbit(i)) ans += f[i];
return ans;
}
int main() {
cin >> n >> m;
lol a;
for (int i = 1; i <= n; i++) scanf("%lld", &a),
add(i, a);
lol flag,
x,
y,
k;
for (int i = 1; i <= m; i++) {
scanf("%lld%lld", &flag, &x);
if (flag == 1) {
scanf("%lld", &k);
add(x, k);
}
if (flag == 2) {
scanf("%lld", &y);
printf("%lld\n", getsum(y) - getsum(x - 1));
}
}
return 0;
}
四,二分图 - 匈牙利算法
//dinic
#include < queue > #include < cstdio > #include < cstring > #include < iostream > using namespace std;
int cnt = -1,
depth[10010],
cur[10010],
s,
t,
n,
m;
int next[200010],
head[10010],
v[200010],
w[200010];
int dfs(int u, int flow) {
if (u == t) return flow;
for (int & i = cur[u]; i != -1; i = next[i]) {
if ((w[i] != 0) && (depth[v[i]] == depth[u] + 1)) {
int di = dfs(v[i], min(flow, w[i]));
if (di > 0) {
w[i] -= di;
w[i ^ 1] += di;
return di;
}
}
}
return 0;
}
bool bfs() {
queue < int > q;
memset(depth, 0, sizeof(depth));
while (!q.empty()) q.pop();
q.push(s);
depth[s] = 1;
do {
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = next[i]) {
if ((w[i] > 0) && (depth[v[i]] == 0)) {
q.push(v[i]);
depth[v[i]] = depth[u] + 1;
}
}
} while (! q . empty ());
if (depth[t] > 0) return 1;
return 0;
}
int dinic() {
int ans = 0;
while (bfs()) {
for (int i = 1; i <= n; i++) cur[i] = head[i];
while (int d = dfs(s, 3e8)) ans += d;
}
return ans;
}
int main() {
int a,
b,
c;
cin >> n >> m >> s >> t;
memset(head, -1, sizeof(head));
memset(next, -1, sizeof(next));
while (m--) {
scanf("%d%d%d", &a, &b, &c);
cnt++;
v[cnt] = b;
w[cnt] = c;
next[cnt] = head[a];
head[a] = cnt;
cnt++;
v[cnt] = a;
w[cnt] = 0;
next[cnt] = head[b];
head[b] = cnt;
}
cout << dinic() << endl;
return 0;
}
五,扩展欧几里得
//eft_xyl
#include < cstdio > #include < cstring > #include < iostream > using namespace std;
int n,
m,
e,
girl[1005];
bool used[1005],
line[1005][1005];
bool find(int x) {
for (int j = 1; j <= m; j++) if (line[x][j] && !used[j]) {
used[j] = 1;
if (!girl[j] || find(girl[j])) {
girl[j] = x;
return 1;
}
}
return 0;
}
int main() {
int x,
y;
cin >> n >> m >> e;
for (int i = 1; i <= e; i++) scanf("%d%d", &x, &y),
line[x][y] = 1;
e = 0;
for (int i = 1; i <= n; i++) {
if (find(i)) e++;
memset(used, 0, sizeof(used));
}
cout << e << endl;
return 0;
}
六,假的字符串 Hash, 其实是 map
//exgcd
#include < cstdio > #include < cstring > #include < iostream > using namespace std;
void exgcd(int a, int b, int & x, int & y) {
if (!b) x = 1,
y = 0;
else {
exgcd(b, a % b, y, x);
y -= x * (a / b);
}
}
int main() {
int a,
b,
x,
y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << (x % b + b) % b << endl;
return 0;
}
七,克鲁斯卡尔
//jia de hash,zhe shi map!
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n;
string s;
map <string,int> mp;
int main()
{
cin>>n;int ans=0;
for (int i=1;i<=n;i++) {
cin>>s;
if (!mp.count(s)) ans++,mp[s]=1;
}
cout<<ans<<endl;
return 0;
}
八,LCA - 倍增
//kruskal
#include < cstdio > #include < cstring > #include < iostream > #include < algorithm > using namespace std;
int n,
m;
int fa[5001];
struct ed {
int f,
t,
w;
}
e[400010];
bool cmp(ed a, ed b) {
return a.w < b.w;
}
void init() {
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int a) {
if (a == fa[a]) return a;
return fa[a] = find(fa[a]);
}
void unionset(int a, int b) {
int u = find(a),
v = find(b);
if (u != v) fa[u] = v;
}
bool same(int u, int v) {
return find(u) == find(v);
}
void kruskal() {
int res = 0;
init();
int cnt = 0;
sort(e + 1, e + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
if (!same(e[i].f, e[i].t)) {
res += e[i].w;
unionset(e[i].f, e[i].t); ++cnt;
}
if (cnt == n - 1) break;
}
cout << res << endl;
}
int main() {
cin >> n >> m;
int x,
y,
w;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &w);
e[i].f = x;
e[i].t = y;
e[i].w = w;
}
kruskal();
return 0;
}
九,构造最长公共子序列 LCS
//lca-ST
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,ss;
int dep[500010];
int dpt[500010][30];
int cnt;
int o[1000010];
int s[1000010][2];
//lsqxx!!!
void jia(int x,int y)
{
s[++cnt][1]=o[x];
s[cnt][0]=y;o[x]=cnt;
}
void dfs(int x,int d)
{
dep[x]=d;
for (int i=o[x];i;i=s[i][1]) {
int y=s[i][0];
if (!dep[y]) {
dpt[y][0]=x;
dfs(y,d+1);
}
}
}
void init()
{
for (int j=1;j<=19;j++)
for (int i=1;i<=n;i++)
dpt[i][j]=dpt[dpt[i][j-1]][j-1];
}
int lca(int a,int b)
{
if (dep[a]<dep[b]) swap(a,b);
for (int j=19;j>=0;j--)
if (dep[a]-(1<<j)>=dep[b]) a=dpt[a][j];
if (a!=b) {
for (int j=19;j>=0;j--)
if (dpt[a][j]!=dpt[b][j])
a=dpt[a][j],b=dpt[b][j];
a=dpt[a][0];
}
return a;
}
int main()
{
int x,y;
cin>>n>>m>>ss;
for (int i=1;i<n;i++) {
scanf("%d%d",&x,&y);
jia(x,y);jia(y,x);
}
dfs(ss,1);init();
for (int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
/*功能:计算最优值
//只能打印一个最长公共子序列
#include <iostream>
using namespace std;
const int X = 100, Y = 100; //串的最大长度
char result[X+1]; //用于保存结果
int count=0; //用于保存公共最长公共子串的个数
*参数:
* x:字符串x
* y:字符串y
* b:标志数组
* xlen:字符串x的长度
* ylen:字符串y的长度
*返回值:最长公共子序列的长度
十,归并排序求逆序对
* */
int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
{
int i = 0;
int j = 0;
int c[X+1][Y+1];
for (i = 0; i<=xlen; i++)
{
c[i][0]=0;
}
for (i = 0; i <= ylen; i++ )
{
c[0][i]=0;
}
for (i = 1; i <= xlen; i++)
{
for (j = 1; j <= ylen; j++)
{
if (x[i - 1] == y[j - 1])
{
c[i][j] = c[i-1][j-1]+1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
if(c[i-1][j] <= c[i][j-1])
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
cout << "计算最优值效果图如下所示:" << endl;
for(i = 1; i <= xlen; i++)
{
for(j = 1; j < ylen; j++)
{
cout << c[i][j] << " ";
}
cout << endl;
}
return c[xlen][ylen];
}
void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_Len)
{
if (i ==0 || j==0)
{
return;
}
if(b[i][j]== 1)
{
current_Len--;
result[current_Len]=x[i- 1];
Display_Lcs(i-1, j-1, x, b, current_Len);
}
else
{
if(b[i][j] == 2)
{
Display_Lcs(i-1, j, x, b, current_Len);
}
else
{
if(b[i][j]==3)
{
Display_Lcs(i, j-1, x, b, current_Len);
}
else
{
Display_Lcs(i-1,j,x,b, current_Len);
}
}
}
}
int main(int argc, char* argv[])
{
string x = "ABCBDAB";
string y = "BDCABA";
int xlen = x.length();
int ylen = y.length();
int b[X + 1][Y + 1];
int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
cout << lcs_max_len << endl;
Display_Lcs( xlen, ylen, x, b, lcs_max_len );
/ / 打印结果如下所示
for (int i = 0; i < lcs_max_len; i++) {
cout << result[i];
}
cout << endl;
return 0;
}
十一,线段树
//msort_nxd
#include < cstdio > #include < cstring > #include < iostream > using namespace std;
int ans,
n,
a[100010],
r[100010];
void msort_nxd(int s, int t) {
if (s == t) return;
int mid = s + t >> 1;
msort_nxd(s, mid);
msort_nxd(mid + 1, t);
int i = s,
j = mid + 1,
k = s;
while (i <= mid && j <= t) {
if (a[i] <= a[j]) {
r[k] = a[i];
i++;
k++;
} else {
r[k] = a[j];
j++;
k++;
ans += mid - i + 1;
}
}
while (i <= mid) r[k++] = a[i++];
while (j <= t) r[k++] = a[j++];
for (int q = s; q <= t; q++) a[q] = r[q];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
msort_nxd(1, n);
cout << ans << endl;
return 0;
}
十二,
//segment
#include < cstdio > #include < cstring > #include < iostream > #define ll(x)((x) << 1)#define rr(x)((x) << 1 | 1) using namespace std;
typedef long long lol;
lol n,
m,
a[100010];
lol sgm[100010 * 4],
lazy[100010 * 4];
void shang(lol r) {
sgm[r] = sgm[ll(r)] + sgm[rr(r)];
}
void xia(lol r, lol z, lol y) {
int k = z + y >> 1;
lazy[ll(r)] += lazy[r];
lazy[rr(r)] += lazy[r];
sgm[ll(r)] += (k - z + 1) * lazy[r];
sgm[rr(r)] += (y - k) * lazy[r];
lazy[r] = 0;
}
void js(lol r, lol z, lol y) {
if (z == y) {
sgm[r] = a[z];
return;
}
int k = z + y >> 1;
js(ll(r), z, k);
js(rr(r), k + 1, y);
shang(r);
}
void qjxg(lol r, lol z, lol y, lol zz, lol yy, lol v) {
if (z > yy || y < zz) return;
if (z >= zz && y <= yy) {
lazy[r] += v;
sgm[r] += (y - z + 1) * v;
return;
}
if (lazy[r]) xia(r, z, y);
int k = z + y >> 1;
if (z <= k) qjxg(ll(r), z, k, zz, yy, v);
if (y > k) qjxg(rr(r), k + 1, y, zz, yy, v);
shang(r);
}
lol cx(lol r, lol z, lol y, lol zz, lol yy) {
if (z > yy || y < zz) return 0;
if (z >= zz && y <= yy) return sgm[r];
int k = z + y >> 1;
if (lazy[r]) xia(r, z, y);
return cx(ll(r), z, k, zz, yy) + cx(rr(r), k + 1, y, zz, yy);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
js(1, 1, n);
lol flag,
x,
y,
k;
for (int i = 1; i <= m; i++) {
scanf("%lld", &flag);
if (flag == 1) {
scanf("%lld%lld%lld", &x, &y, &k);
qjxg(1, 1, n, x, y, k);
} else {
scanf("%lld%lld", &x, &y);
cout << cx(1, 1, n, x, y) << endl;
}
}
return 0;
}
十三,
SPFA
//SPFA
#include < queue > #include < cstdio > #include < cstring > #include < iostream > using namespace std;
int n,
m,
st,
d[10010];
int cnt;
int o[500010];
int s[500010][3];
//lsqxx!!!
void jia(int x, int y, int c) {
s[++cnt][1] = o[x];
s[cnt][0] = y;
s[cnt][2] = c;
o[x] = cnt;
}
queue < int > q;
bool v[10010];
void SPFA() {
for (int i = 1; i <= n; i++) d[i] = 2147483647;
v[st] = 1;
q.push(st);
d[st] = 0;
while (!q.empty()) {
int x = q.front();
for (int i = o[x]; i; i = s[i][1]) {
int y = s[i][0];
if (d[y] > d[x] + s[i][2]) {
d[y] = d[x] + s[i][2];
if (!v[y]) {
v[y] = 1;
q.push(y);
}
}
}
q.pop();
v[x] = 0;
}
}
int main() {
int x,
y,
c;
cin >> n >> m >> st;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &c);
jia(x, y, c);
}
SPFA();
for (int i = 1; i <= n; i++) {
printf("%d ", d[i]);
}
cout << endl;
return 0;
}
树链剖分
十四,最小费用最大流
//shupou
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll(x) ((x)<<1)
#define rr(x) ((x)<<1|1)
using namespace std;
typedef long long l;
const int N=100010;l n,m,r,p,cnt,dfscnt;
l d[N],id[N],f[N],son[N],top[N],siz[N],sgm[N*4],lazy[N*4],a[N],w[N],o[N],s[N*2][2];
void jia(l x,l y) {s[++cnt][1]=o[x];s[cnt][0]=y;o[x]=cnt;}
void dfs(l x,l fa,l dep)
{
f[x]=fa;d[x]=dep;siz[x]=1;l mm=-1;
for (int i=o[x];i;i=s[i][1]) {
if (s[i][0]!=fa) {
dfs(s[i][0],x,dep+1);siz[x]+=siz[s[i][0]];
if (siz[s[i][0]]>mm) son[x]=s[i][0],mm=siz[s[i][0]];
}
}
}
void build(l x,l tp)
{
id[x]=++dfscnt;top[x]=tp;a[dfscnt]=w[x];
if (son[x]) build(son[x],tp);
for (int i=o[x];i;i=s[i][1])
if ((s[i][0]!=f[x])&&(son[x]!=s[i][0])) build(s[i][0],s[i][0]);
}
void xia(l r,l z,l y)
{
l k=z+y>>1;lazy[ll(r)]+=lazy[r];lazy[rr(r)]+=lazy[r];
sgm[ll(r)]+=(k-z+1)*lazy[r];
sgm[rr(r)]+=(y-k)*lazy[r];
sgm[ll(r)]%=p;sgm[ll(r)]%=p;lazy[r]=0;
}
void js(l r,l z,l y)
{
if (z==y) {sgm[r]=a[z];if (sgm[r]>p) sgm[r]%=p;return;}
l k=z+y>>1;js(ll(r),z,k);js(rr(r),k+1,y);sgm[r]=(sgm[ll(r)]+sgm[rr(r)])%p;
}
void qjxg(l r,l z,l y,l zz,l yy,l v)
{
if (z>yy||y<zz) return;
if (z>=zz&&y<=yy) {
lazy[r]+=v;sgm[r]+=(y-z+1)*v;return;}
if (lazy[r]) xia(r,z,y);l k=z+y>>1;
if (z<=k) qjxg(ll(r),z,k,zz,yy,v);if (y>k) qjxg(rr(r),k+1,y,zz,yy,v);
sgm[r]=(sgm[ll(r)]+sgm[rr(r)])%p;
}
l cx(l r,l z,l y,l zz,l yy)
{
if (z>yy||y<zz) return 0;
if (z>=zz&&y<=yy) return sgm[r]%p;
l k=z+y>>1;if (lazy[r]) xia(r,z,y);
return (cx(ll(r),z,k,zz,yy)+cx(rr(r),k+1,y,zz,yy))%p;
}
l qiulu(l x,l y)
{
l ans=0;while (top[x]!=top[y]) {
if (d[top[x]]<d[top[y]]) swap(x,y);
ans+=cx(1,1,n,id[top[x]],id[x]);ans%=p;x=f[top[x]];
}
if (d[x]>d[y]) swap(x,y);ans+=cx(1,1,n,id[x],id[y]);ans%=p;
return ans;
}
void jialu(l x,l y,l v)
{
v%=p;while (top[x]!=top[y]) {
if (d[top[x]]<d[top[y]]) swap(x,y);
qjxg(1,1,n,id[top[x]],id[x],v);x=f[top[x]];
}
if (d[x]>d[y]) swap(x,y);qjxg(1,1,n,id[x],id[y],v);
}
int main()
{
l x,y,v,flag;cin>>n>>m>>r>>p;for (int i=1;i<=n;i++) scanf("%lld",&w[i]);
for (int i=1;i<n;i++) {scanf("%lld%lld",&x,&y);jia(x,y);jia(y,x);}dfs(r,0,1);build(r,r);js(1,1,n);
for (int i=1;i<=m;i++) {scanf("%lld",&flag);
if (flag==1) {scanf("%lld%lld%lld",&x,&y,&v);jialu(x,y,v);}
if (flag==2) {scanf("%lld%lld",&x,&y);printf("%lld\n",qiulu(x,y));}
if (flag==3) {scanf("%lld%lld",&x,&v);v%=p;qjxg(1,1,n,id[x],id[x]+siz[x]-1,v);}
if (flag==4) {scanf("%lld",&x);printf("%lld\n",cx(1,1,n,id[x],id[x]+siz[x]-1)%p);}
}
return 0;
}
十五,
//zxfyzdl
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=5010,M=100010,inf=2e9;
int head,tail,cnt=-1,n,m,s,t,cost=0;
int q[N*10],v[N],ss[M*2][4],o[N],d[N],vis[N];
void jia(int a,int b,int c,int cc)
{
//ss[i][0]-->to;ss[i][1]-->next;ss[i][2]-->flow;ss[i][3]-->cost;
ss[++cnt][0]=b;ss[cnt][1]=o[a];
ss[cnt][2]=c;ss[cnt][3]=cc;o[a]=cnt;
ss[++cnt][0]=a;ss[cnt][1]=o[b];
ss[cnt][2]=0;ss[cnt][3]=-cc;o[b]=cnt;
}
int dfs(int x,int flow)
{
v[x]=1;int rest=0;if (x==t) return flow;
for (int i=o[x];i!=-1;i=ss[i][1]) {
if ((d[ss[i][0]]==d[x]-ss[i][3])&&(v[ss[i][0]]==0)&&(ss[i][2]!=0)) {
int di=dfs(ss[i][0],min(flow-rest,ss[i][2]));
if (di>0) {rest+=di;ss[i][2]-=di;ss[i^1][2]+=di;}
}
}
return rest;
}
bool spfa()
{
for (int i=1;i<=n;i++) d[i]=inf,vis[i]=0;
head=1;tail=2;q[1]=t;d[t]=0;vis[t]=1;
while (head!=tail) {
int u=q[head];
for (int i=o[u];i!=-1;i=ss[i][1]) {
if ((d[ss[i][0]]>d[u]-ss[i][3])&&(ss[i^1][2]!=0)) {
d[ss[i][0]]=d[u]-ss[i][3];
if (!vis[ss[i][0]]) {
vis[ss[i][0]]=1;q[tail++]=ss[i][0];if (tail==n+1) tail=1;
}
}
}
q[head++]=0;vis[u]=0;if (head==n+1) head=1;
}
return d[s]!=inf;
}
void FU_DUI_SUAN_FA_BO_DA_JING_SHEN()
{
int ans=0,cntt=1;
while (spfa()) {
v[t]=1;
while (v[t]) {
memset(v,0,sizeof(v));
int l=dfs(s,inf);ans+=l;cost+=l*d[s];
}
}
cout<<ans<<" "<<cost<<endl;
}
int main()
{
int a,b,c,cc;
memset(o,-1,sizeof(o));
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++) {
scanf("%d%d%d%d",&a,&b,&c,&cc);
jia(a,b,c,cc);
}
FU_DUI_SUAN_FA_BO_DA_JING_SHEN();
return 0;
}
堆 (手打)
十六,优先队列 (STL)
//heap-xiao
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,flag,heap[1000010],heapsize;
void jiaru(int d)
{
int now,next;heap[++heapsize]=d;now=heapsize;
while (now>1) {
next=now>>1;if (heap[now]>=heap[next]) break;
swap(heap[now],heap[next]);now=next;
}
return;
}
int shanchu_quchu()
{
int now,next,res;res=heap[1];heap[1]=heap[heapsize--];now=1;
while (now*2<=heapsize) {
next=now*2;
if (next<heapsize&&heap[next+1]<heap[next]) next++;
if (heap[now]<=heap[next]) break;swap(heap[now],heap[next]);
now=next;
}
return res;
}
int main()
{
cin>>n;int x;
while (n--) {
scanf("%d",&flag);
if (flag==1) {scanf("%d",&x);jiaru(x);}
if (flag==2) {printf("%d\n",heap[1]);}
if (flag==3) {int daiti=shanchu_quchu();}
}
return 0;
}
十七,迪杰斯特拉 (堆优化版本)
//priority_queue
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,flag,a;
priority_queue <int> heap;
int main() {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>flag;
if (flag==1) {
cin>>a;
heap.push(-a);
}
else if (flag==2) {
int f=heap.top();
cout<<-f<<endl;
}
else heap.pop();
}
return 0;
}
十八,迪杰斯特拉 (线段树版本)
//dijkstra-dyh
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 10010
using namespace std;
typedef pair<int,int>Pair;
struct node {
int u,w,v,next;
}e[500010];
int dis[MAXN],st[MAXN];
bool flag[MAXN];
int tot,start,n,m,x,y,z;
void add(int x,int y,int z)
{
e[++tot].u=x;e[tot].v=y;
e[tot].w=z;
e[tot].next=st[x];st[x]=tot;
}
int dijsktra(int start)
{
memset(dis,127,sizeof dis);
memset(flag,0,sizeof flag);
dis[start]=0;priority_queue< Pair,vector<Pair>,greater<Pair> >que;
que.push(make_pair(dis[start],start));
while (!que.empty()) {
Pair now=que.top();que.pop();
if (flag[now.second]) continue;
flag[now.second]=1;
for (int i=st[now.second];i;i=e[i].next)
if (dis[now.second]+e[i].w<dis[e[i].v]) {
dis[e[i].v]=dis[now.second]+e[i].w;
if (!flag[e[i].v]) que.push(make_pair(dis[e[i].v],e[i].v));
}
}
for (int i=1;i<=n;i++) {
if (dis[i]==2139062143) dis[i]=2147483647;
printf("%d ",dis[i]);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&start);
for (int i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dijsktra(start);
}
未完待续... 从 2017 年暑假到现在手打的模板↑_↑
//dijktra-xds
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =10007;
const int maxm = 500007;
const int INF = 0x7fffffff;
int n,m;
inline int read()
{
int x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
struct node{
int v,next,w;
}edge[maxm];
int num=0,head[maxn];
inline void add_edge(int a,int b,int c) {
edge[++num].v=b;edge[num].w=c;edge[num].next=head[a];head[a]=num;
}
int dis[maxn],ans[maxn],s,t;
int tree[maxn<<2],leaf;
inline int check(int i,int j) {
return dis[i]<dis[j]?i:j;
}
inline void build() {
std::memset(dis,0x3f,sizeof dis);
for (leaf=1;leaf<=n;leaf<<=1);--leaf;
for (int i=1;i<=n;++i)tree[leaf+i]=i;
}
inline void modify(int x,int y) {
dis[x]=y,x+=leaf,x>>=1;
while(x) tree[x]=check(tree[x<<1],tree[x<<1|1]),x=x>>1;
}
void dijkstra(int s) {
build();dis[s]=0;int u=s;
for (int i=1;i<=n;++i) {
ans[u]=dis[u];
const int disu=dis[u];
modify(u,INF);
for (int j=head[u];j;j=edge[j].next){
int v=edge[j].v;
if (dis[v]<INF&&dis[v]>disu+edge[j].w)
modify(v,disu+edge[j].w);
}
u=tree[1];
}
}
inline void put(int x)
{
if (x>9) put(x/10);
putchar(x%10+48);
}
int main() {
int k;
n=read(),m=read(),k=read();
for (int a,b,c,i=1;i<=m;++i) {
a=read(),b=read(),c=read();
add_edge(a,b,c);
}
dijkstra(k);
for (int i=1;i<=n;++i) {
if (dis[i]==0x3f3f3f3f) ans[i]=INF;
put(ans[i]);putchar(' ');
}
putchar('\n');
return 0;
}
来源: http://www.bubuko.com/infodetail-2460635.html