oToToT的code收藏區

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_m 題目大意: 給一個 $N$ 個點 $M$ 條邊的圖，對於所有點 $u$ 求問強迫經過點 $u$ 時 $1$ 走到 $n$ 的最短路是多長。 從 $1$ 跟 $N$ 分別做一次 Dijkstra 就好了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; const lld INF = static_cast<lld>(1) << 60; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, lld>>> g(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; g[--u].emplace_back(--v, w); g[v].emplace_back(u, w); } auto shortest_path = [&g] (int s, vector<lld> &d) { vector<bool> vis(d.size()); fill(d.begin(), d.end(), INF); priority_queue<pair<lld,int>> pq; d[s] = 0; pq.emplace(-d[s], s); while (n...

題目連結: http://tioj.infor.org/problems/1847 題目看了一下下才看懂，原來就是給你一張圖問你最短距離小於D的點權和。那要求最短路徑就寫個dijkstra就好，然後再掃一下看某個點距離是不是小於D，是就加點權，不是就不加。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; const int INF = (1<<30) + 5; vector<int> G[N]; int dis[N], val[N]; bitset<N> visited; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m, d; cin>>n>>m; for(int i=0;i<n;i++) cin>>val[i]; for(int i=0;i<m;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } cin>>d; fill(dis, dis+n, INF); priority_queue<PII,vector<PII>,greater<PII>> pq; dis[0]=0; pq.push({dis[0], 0}); while(!pq.empty()){ int u = pq.top().SS; pq.pop(); ...

題目連結: http://tioj.infor.org/problems/1212 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <bits/stdc++.h> using namespace std; #define INF 999999 #define N 500 int graph[N + 10][N + 10]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n!=0||m!=0){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j]=INF; for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); graph[a][b]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]); int mm=INF; for(int i=1;i<=n;i++) mm = min(graph[i][i], mm); if(mm==INF) puts("0"); ...

題目連結: http://tioj.infor.org/problems/1096 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <stdio.h> #define INF 9999999 int graph[101][101]; int main(){ int n; scanf("%d",&n); while(n!=0){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&graph[i][j]); if(graph[i][j]==0)graph[i][j]=INF; } } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(graph[i][k]+graph[k][j] < graph[i][j]) graph[i][j] =graph[i][k]+graph[k][j]; int min=INF; for(int i=0;i<n;i++) if(graph[i][i]<min) min=graph[i][i]; if(min==INF) puts("-1"); else printf("%d\n...

題目連結: http://tioj.infor.org/problems/1509 裸單點源最短路徑，直接寫個dijkstra就好了 #include <stdio.h> #include <vector> #include <queue> #include <bitset> #include <algorithm> using std::vector; using std::priority_queue; using std::bitset; using std::swap; struct node{ int vertex; int dis; }; class cmp{ public: bool operator ()(node a, node b){ return a.dis>b.dis; } }; bitset<1000000 + 10> poped; vector<node> forward[1000000 + 10], backward[1000000 + 10]; int dis[1000000 + 10]; priority_queue<node,vector<node>,cmp> pq; int main(){ //input int m,n; unsigned long long ans=0; scanf("%d %d",&m,&n); for(int i=0;i<n;i++){ node OAO; int a; scanf("%d %d %d",&a,&OAO.vertex,&OAO.dis); forwa...