1 solutions
-
0
C++ :
#include <iostream> #include <cstdio> #include <cstring> #include <climits> using namespace std; struct bian{ int y,next,len; }e[45001]={0}; int n,i,j,k,m,tot,x,y,z,st,en,o,tp,p,max,sum; int f[1001]={0},g[1001]={0},ng[1001]={0},d[1001]={0},dist[1001]={0}; bool v[1001]={0}; int q[100001]={0}; void swap(int &x,int &y) { int tp; tp=x; x=y; y=tp; } bool spfa(int x) { bool res=false; int i,j,k,st,en,o,p; for(int i=1;i<=n;i++) { dist[i]=INT_MAX; } st=0, en=1, q[en]=x, v[x]=true; d[x]=1, dist[x]=0; while(st!=en) { if(st==100000) st=0; st++; o=g[q[st]]; v[q[st]]=false; while(o!=0) { p=e[o].y; if(dist[p]>dist[q[st]]+e[o].len) { dist[p]=dist[q[st]]+e[o].len; if(!v[p]) { q[++en]=p; v[p]=true; d[p]++; if(d[p]>n) return true; } } o=e[o].next; } } } void init() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { cin>>x>>y>>z; if(y<x) swap(x,y); tot++; e[tot].y=y; e[tot].len=z; e[tot].next=g[x]; g[x]=tot; } for(int i=1;i<=k;i++) { cin>>x>>y>>z; tot++; e[tot].y=x; e[tot].len=-z; e[tot].next=g[y]; g[y]=tot; } for(int i=2;i<=n;i++) { tot++; e[tot].y=i-1; e[tot].next=g[i]; e[tot].len=0; g[i]=tot; } if(spfa(1)) { cout<<-1<<endl; return; } if(dist[n]==INT_MAX) { cout<<-2<<endl; return; } cout<<dist[n]<<endl; return; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init(); return 0; }
- 1
Information
- ID
- 17502
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By