Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
3.0 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define EPS 1e-9
#define mod 1000000007
#define over 10000000000
#define sz(m) (ll)(m.size())
#define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
bool sortbysecdesc(pair<int, int> &a, pair<int, int> &b)
{
  if (a.first == b.first)
    return a.second > b.second;
  else
    return a.first < b.first;
}
#define fixed(n) fixed << setprecision(n)
const ll inf = 1e18 + 5;
// vector< vector <int> > nums( n , vector<int> (m)) ;
//  priority_queue<int, vector<int>, greater<int> > pq ;
template <typename T = int>
istream &operator>>(istream &in, vector<T> &v)
{
  for (T &i : v)
    in >> i;
  return in;
}
template <typename T = int>
ostream &operator<<(ostream &out, const vector<T> &v)
{
  for (const T &x : v)
    out << x << ' ';
  return out;
}

void lol()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin), freopen("outputt.txt", "w", stdout), freopen("error.txt", "w", stderr);
#endif
}
double log(double base, double x)
{
  return (log(x) / log(base));
}

// count(begin(nums), end(nums), 0);
bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
  if (a.first > b.first)
    return (a.second > b.second);
  else
    return (a.second < b.second);
}
ll ncr(ll n, ll r)
{
  vector<ll> inv(r + 1);
  ll ans = 1;
  inv[0] = 1;
  if (r + 1 >= 2)
    inv[1] = 1;
  for (int i = 2; i <= r; i++)
    inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  // to get 1 / (r!)
  for (int i = 2; i <= r; i++)
    ans = ((ans % mod) * (inv[i] % mod)) % mod;
  for (int i = n; i >= (n - r + 1); i--)
    ans = ((ans % mod) * (i % mod)) % mod;
  return ans;
}
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
ll fast_power(ll base, ll p)
{
  if (!p)
    return 1;
  unsigned ll ret = fast_power(base, p / 2);
  ret = (ret * ret);
  if (p % 2)
    ret = (ret * base);
  return ret;
}
int add(ll a, ll b)
{
  return (a + b) % mod;
}
///////////////////////////////////////////////////////////////////
/*
bfs for min path by char
bfs for get char
 // 2
  a  - z , a -  b , c - d
*/

int n, m;
vector<pair<int, char>> adj[200000 + 10];
int dist[200000 + 10];
int vis[200000 + 10];
// min path
void bfs(int node)
{
  queue<int> q;
  q.push(node);
  vis[node] = 1;
  while (!q.empty())
  {
    int v = q.front();
    q.pop();
    for (auto &[i, j] : adj[v])
    {
      if (!vis[i])
      {
        vis[i] = 1;
        dist[i] = dist[v] + 1;

        q.push(i);
      }
    }
  }
} 
// bfs2 like build of dp  
int parent [200000 + 10] ;
vector < int > path ; 
string s ; 
vector < int > bfs2(int node) 
{
   
}

int main()
{
  lol();
  cin >> n >> m;
  for (int i = 0; i < m; i++)
  {
    int u, v, c;
    cin >> u >> v >> c;
    adj[u].push_back({v, c});
    adj[v].push_back({u, c});
  }
  // bfs min path
  bfs(n);
   //cout << dist[1] << '\n';
  path.push_back(1) ; 
}