結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
![]() |
提出日時 | 2021-02-22 23:27:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,629 bytes |
コンパイル時間 | 5,232 ms |
コンパイル使用メモリ | 262,892 KB |
最終ジャッジ日時 | 2025-01-19 03:41:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 TLE * 25 MLE * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;#define all(s) (s).begin(),(s).end()#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second#define P pair<ll,ll>//const ll mod = 998244353;const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;void YesNo(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void YESNO(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }struct graph{struct edge{ll to,cost;};ll v;vector<vector<edge>> g;vector<ll> d;vector<bool> negative;vector<bool> diameter;vector<ll> topological_sort;ll diametercost;bool bipartitecheck;vector<ll> bipartite;graph(ll n){init(n);}void init(ll n){v=n;g.resize(n);d.resize(n);negative.resize(n);diameter.resize(n);bipartite.resize(n);for(int i=0;i<v;i++){d[i]=inf;bipartite[i]=-1;negative[i]=false;diameter[i]=false;}}void addedge(ll s,ll t,ll cost){edge e;e.to=t;e.cost=cost;g[s].push_back(e);}void dijkstra(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;priority_queue<P,vector<P>,greater<P>> que;que.push(P(0,s));while(!que.empty()){P p=que.top();que.pop();ll V=p.second;if(d[V]<p.first) continue;for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;que.push(P(d[e.to],e.to));}}}}void BellmanFord(ll s){for(int i=0;i<v;i++){d[i]=inf;negative[i]=false;}d[s]=0;for(int i=0;i<v;i++){for(int V=0;V<v;V++){if(d[V]==inf){continue;}for(auto e:g[V]){if(d[e.to]>d[V]+e.cost){d[e.to]=d[V]+e.cost;if(i==v-1){negative[e.to]=true;negative[V]=true;}}}}}}void dfs(ll s){for(int i=0;i<v;i++){d[i]=inf;}d[s]=0;dfs2(s,-1);}void dfs2(ll s,ll v){for(auto e:g[s]){if(e.to==v) continue;if(d[e.to]>d[s]+e.cost){d[e.to]=d[s]+e.cost;dfs2(e.to,s);}}}void treediameter(){dfs(0);ll p=0;ll q=0;for(int i=0;i<v;i++){if(q<d[i]){q=d[i];p=i;}}diameter[p]=true;dfs(p);ll p2=0;ll q2=0;for(int i=0;i<v;i++){if(q2<d[i]){q2=d[i];p2=i;}}diameter[p2]=true;diametercost=d[p2];}void Bipartite(){Bipartitedfs(0);}void Bipartitedfs(ll s,ll cur=0){bipartite[s]=cur;for(auto e:g[s]){if(bipartite[e.to]!=-1){if((bipartite[e.to]==bipartite[s])^(!e.cost%2)){bipartitecheck=false;}}else{if(e.cost%2){Bipartitedfs(e.to,1-cur);}else{Bipartitedfs(e.to,cur);}}}}void topologicalsort(){for(int i=0;i<v;i++){d[i]=0;}for(int i=0;i<v;i++){if(d[i]) continue;topologicaldfs(i);}rever(topological_sort);}void topologicaldfs(ll a){d[a]=1;for(auto e:g[a]){if(d[e.to]) continue;topologicaldfs(e.to);}topological_sort.push_back(a);}};int main() {/* mod は 1e9+7 */ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(10);ll n,m;cin>>n>>m;graph g(n);for(int i=0;i<m;i++){ll k,c;cin>>k>>c;vector<ll> t(k);vcin(t);for(int j=0;j<k;j++){for(int s=j+1;s<k;s++){g.addedge(t[j]-1,t[s]-1,t[j]+t[s]-(t[j]+t[s])/2+c);g.addedge(t[s]-1,t[j]-1,t[j]+t[s]-(t[j]+t[s])/2+c);}}}g.dijkstra(0);if(g.d[n-1]>inf/2){cout<<-1<<endl;}else{cout<<g.d[n-1]<<endl;}}