Please give the space and time complexity of the two codes below and the reason why. Example: O(N), O(n log n), O(N^2)...etc. Code 1: #include #include #include using namespace std; const int Inf = 1e9; const int maxstars = 1005; struct Edge { int to, c; }; vector edges[maxstars]; int jarak[maxstars]; int main() { int T; scanf("%d",&T); while (T--) { int N, E; scanf("%d %d",&N,&E); for (int i = 0; i < N; ++i) { edges[i].clear(); jarak[i] = Inf; } Edge e; while (E--) { int x; cin >> x >> e.to >> e.c; edges[x].push_back(e); } for (int t = 0; t < N - 1; ++t) { for (int j = 0; j < N; ++j) { for (int e = 0; e < edges[j].size(); ++e) { jarak[edges[j][e].to] = min(jarak[edges[j][e].to], jarak[j] + edges[j][e].c); } } } bool bisaturun = false; for (int j = 0; j < N; ++j) { for (int e = 0; e < edges[j].size(); ++e) { bisaturun |= jarak[edges[j][e].to] > jarak[j] + edges[j][e].c; } } cout << (bisaturun ? "possible\n" : "not possible\n"); } } Code 2: #include #include #define N 2001 #define MAX 100000000 using namespace std; int a[N], b[N], t[N]; bool BellmanFord(int n, int m); int main() { int Case, n, m; scanf("%d", &Case); while (Case--) { int i; scanf("%d%d", &n, &m); for (i = 0; i < m; i++) scanf("%d%d%d", &a[i], &b[i], &t[i]); puts(BellmanFord(n, m) ? "possible" : "not possible"); } return 0; } bool BellmanFord(int n, int m) { int d[N]; fill(d, d + n, MAX); d[0] = 0; for (int i = 0; i < n - 1; i++) //bellman ford for (int j = 0; j < m; j++) if (d[a[j]] != MAX) if (d[a[j]] + t[j] < d[b[j]]) d[b[j]] = d[a[j]] + t[j]; //negative cycle check for (int j = 0; j < m; j++) if (d[a[j]] + t[j] < d[b[j]]) return true; return false; }
Please give the space and time complexity of the two codes below and the reason why. Example: O(N), O(n log n), O(N^2)...etc.
Code 1:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int Inf = 1e9;
const int maxstars = 1005;
struct Edge
{
int to, c;
};
vector<Edge> edges[maxstars];
int jarak[maxstars];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int N, E;
scanf("%d %d",&N,&E);
for (int i = 0; i < N; ++i)
{
edges[i].clear();
jarak[i] = Inf;
}
Edge e;
while (E--)
{
int x;
cin >> x >> e.to >> e.c;
edges[x].push_back(e);
}
for (int t = 0; t < N - 1; ++t)
{
for (int j = 0; j < N; ++j)
{
for (int e = 0; e < edges[j].size(); ++e)
{
jarak[edges[j][e].to] = min(jarak[edges[j][e].to], jarak[j] + edges[j][e].c);
}
}
}
bool bisaturun = false;
for (int j = 0; j < N; ++j)
{
for (int e = 0; e < edges[j].size(); ++e)
{
bisaturun |= jarak[edges[j][e].to] > jarak[j] + edges[j][e].c;
}
}
cout << (bisaturun ? "possible\n" : "not possible\n");
}
}
Code 2:
#include<cstdio>
#include<algorithm>
#define N 2001
#define MAX 100000000
using namespace std;
int a[N], b[N], t[N];
bool BellmanFord(int n, int m);
int main()
{
int Case, n, m;
scanf("%d", &Case);
while (Case--)
{
int i;
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++)
scanf("%d%d%d", &a[i], &b[i], &t[i]);
puts(BellmanFord(n, m) ? "possible" : "not possible");
}
return 0;
}
bool BellmanFord(int n, int m)
{
int d[N];
fill(d, d + n, MAX);
d[0] = 0;
for (int i = 0; i < n - 1; i++)
//bellman ford
for (int j = 0; j < m; j++)
if (d[a[j]] != MAX)
if (d[a[j]] + t[j] < d[b[j]])
d[b[j]] = d[a[j]] + t[j];
//negative cycle check
for (int j = 0; j < m; j++)
if (d[a[j]] + t[j] < d[b[j]])
return true;
return false;
}
Step by step
Solved in 2 steps
