设为首页 加入收藏

TOP

解析·NOIP·冷门 CLZ最小环(二)
2018-11-05 22:08:29 】 浏览:289
Tags:解析 NOIP 冷门 CLZ 小环
#define pall pair<int,int> using namespace std; inline char get(){ static char buf[300],*p1=buf,*p2=buf; return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++; } inline int read(){ register char c=get();register int f=1,_=0; while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get(); while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get(); return _*f; } struct edge{ int u,v,w,next; }E[maxm]; struct cmp{ operator ()(const pall &a,const pall &b)const{ if(a.Y!=b.Y)return a.Y<b.Y; return a.X<b.X; } }; int p[maxn],eid; inline void init(){ for(register int i=0;i<maxn;i++)p[i]=-1; eid=0; } inline void insert(int u,int v,int w){ E[eid].u=u; E[eid].v=v; E[eid].w=w; E[eid].next=p[u]; p[u]=eid++; } inline void insert2(int u,int v,int w){ insert(u,v,w); insert(v,u,w); } int n,m; int dis[maxn],vis[maxn]; void dijkstra(int u){ pall note; bool wait=1; for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0; dis[u]=0;vis[u]=1; set<pall,cmp> s; s.insert(make_pair(u,0)); for(register int i=0;i<n && s.size();i++){ set<pall,cmp>::iterator it=s.begin(); u=it->X; s.erase(*it); vis[u]=1; for(register int j=p[u];~j;j=E[j].next){ int v=E[j].v; int w=E[j].w; if(dis[v]>dis[u]+w && !vis[v]){ s.erase(make_pair(v,dis[v])); s.insert(make_pair(v,dis[v]=dis[u]+w)); note=make_pair(u,v); } } if(wait){ dis[u]=0x3f3f3f3f; vis[u]=0; wait=0; } } } int u,v,w; int main(){ freopen("1.txt","r",stdin); init(); n=read();m=read(); for(register int i=0;i<m;i++){ u=read();v=read();w=read(); insert(u,v,1); } int ans=0x3f3f3f3f; for(register int i=1;i<=n;i++){ dijkstra(i); ans=min(ans,dis[i]); } cout<<ans<<endl; return 0; }
首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇c/c++ 多线程 unique_lock的使用 下一篇c/c++ 多线程 层级锁

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目