a_pig_of_banana

180

LI冬天
At_sunrise

if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;

if(!st[j])
{
q.push(j);
st[j] = true;
}
}


#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1500010;
int h[N], e[N], w[N], ne[N], idx;
int n, m;

bool b[N];
int dist[N];

void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}

int dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
memset(dist, 0x3f, sizeof dist);

dist[1] = 0;
heap.push({0, 1});

while(heap.size())
{
auto t = heap.top();
heap.pop();

int distance = t.first, ver = t.second;

if(b[ver]) continue;
b[ver] = true;

for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];

if(distance + w[i] < dist[j])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}

if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
ios :: sync_with_stdio(false), cin.tie(0);
memset(h, -1, sizeof h);

cin >> n >> m;
while(m --)
{
int a, b, c;

cin >> a >> b >> c;
}

printf("%d\n", dijkstra());

return 0;
}


# dijkstra 算法 O(N ^ 2)

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0)
#define T true
#define F false

using namespace std;

typedef int I;
typedef bool B;

const I N = 510;

I g[N][N];
I n, m;

B b[N];
I dist[N];

I dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for(I i = 0; i < n - 1; i ++)
{
I t = -1;

for(I j = 1; j <= n; j ++)
if(!b[j] && (t == -1 || dist[t] > dist[j]))
t = j;

for(I j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]);

b[t] = T;
}

if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
cin_Quick;
memset(g, 0x3f, sizeof g);

cin >> n >> m;
while(m --)
{
I a, b, w;

cin >> a >> b >> w;
g[a][b] = min(g[a][b], w);
}

printf("%d\n", dijkstra());

return 0;
}



### 题目描述

#### 样例

##### 输入
3 3
1 2 2
2 3 1
1 3 4

##### 输出
3


1 ≤ n ≤ 500,
1 ≤ m ≤ 1e5,

#### 朴素 dijkstra 算法时间复杂度：

$O(N ^ 2)$

#### C++ 代码

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0)
#define T true
#define F false

using namespace std;

typedef int I;
typedef bool B;

// ---------- 以上是减代码的 TYPEDEF 和 DEFINE （虽然有一点多余）----------

const I N = 510;

I g[N][N];
I n, m;

B b[N];  // 已确定最短路的点
I dist[N];

// 最短路开始！！

I dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;                           // 初始化 dist 数组

for(I i = 0; i < n - 1; i ++)
{
I t = -1;

for(I j = 1; j <= n; j ++)
if(!b[j] && (t == -1 || dist[t] > dist[j]))  // 找出现在不在 b 数组中的， 距离最近的点
t = j;

for(I j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]); // 用 t 去更新其他的点

b[t] = T;  // t 已确定
}

if(dist[n] == 0x3f3f3f3f) return -1;  // 和初始数相同， 说明 1 到 n 无最短路
return dist[n];                       // 否则返回最短路长度
}

int main()
{
cin_Quick;  // cin 加速
memset(g, 0x3f, sizeof g); // 初始化 g 数组

cin >> n >> m;
while(m --)
{
I a, b, w;

cin >> a >> b >> w;
g[a][b] = min(g[a][b], w);  // 由于重边的原因，只需要保留最短的一条边
} // 输入

printf("%d\n", dijkstra());

return 0;
}// over


# 制作不易， 麻烦给颗小星星（￣ω￣）

### 题目描述

#### 样例

##### 输入
3 3
1 2
2 3
1 3

##### 输出
1 2 3


#### C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef queue<int> ns;
typedef int I;

const I N = 100010;
I h[N], e[N], ne[N];
I idx;

I d[N];

I n, m;
ns ans;

void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }

bool topsort()
{
ns q;
I tt = -1;

for(I i = 1; i <= n; i ++)
if(!d[i])
q.push(i), tt ++;

while(q.size())
{
I t = q.front();
ans.push(t);
q.pop();

for(I i = h[t]; i != -1; i = ne[i])
{
int j = e[i];

d[j] --;
if(!d[j]) q.push(j), tt ++;
}
}

return tt == n - 1;
}

I main()
{
ios::sync_with_stdio(false),cin.tie(0);

memset(h, -1, sizeof h);

cin >> n >> m;
while(m --)
{
I a, b;

cin >> a >> b;

d[b] ++;
}

if(topsort())
{
for(I i = 0; i < n; i ++) printf("%d ", ans.front()), ans.pop();
}
else puts("-1");

return 0;
}


# 核对了好几遍 找不出答案

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;
int p[N], d[N];

int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}

return p[x];
}

int main()
{
int n, k, res = 0;

cin >> n >> k;

for(int i = 1; i <= n; i ++) p[i] = i;

while(k --)
{
int D;
int x, y;

cin >> D >> x >> y;

if(x > n || y > n) res ++;
else
{
int px = find(x), py = find(y);

if(D == 1)
{
if(px == py && (d[x] - d[y]) % 3) res ++;
else
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if(px == py && (d[x] - d[y] - 1) % 3) res ++;
else
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}

cout << res << endl;
return 0;
}



# 我这有什么问题吗??!! 有个测试点明明输出和答案一样, 它还WA!!!

#include <iostream>

using namespace std;

const int N =  100010;
int QuickStack[N];

void push(int x){ QuickStack[++ head] = x; }

bool empty(){ return head == 0; }

int main()
{
ios :: sync_with_stdio(false),
cin.tie(0),
cout.tie(0);

int n;

cin >> n;
while(n --){
string que;
int x;

cin >> que;

if(que == "push") cin >> x, push(x);
else if(que == "pop") pop();
else if(que == "query") cout << query() << endl;
else cout << (empty() ? "Yes" : "No") << endl;
}

return 0;
}


 #include <iostream> #include <vector> #define quik ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; vector<int> add(vector<int> &A, vector<int> &B){ if(A.size() < B.size()) return add(B, A); vector<int> ans; int t = 0; for(int i = 0; i < A.size(); i ++){ t += A[i]; if(B.size() > i) t += B[i]; ans.push_back(t % 10); t /= 10; } if(t) ans.push_back(t); return ans; } int main(){ quik; string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0'); auto ans = add(A, B); for(int i = ans.size() - 1; i >= 0; i --) cout << ans[i]; cout << endl; return 0; }