?

---

?看完題目后就覺得 哈，好裸的最短路，寫Dijstra加優(yōu)先隊列優(yōu)化吧（本題會卡SPFA，SPFA當(dāng)場去世）時是這樣的

分?jǐn)?shù)君去世? ?

在此警告自己，數(shù)組范圍一定一定要想清楚后再寫，N和M不要弄混，要輸出“Inf”的情況一定要把特判條件寫清楚，范圍不要制定的那么不清楚嘛（結(jié)果錯了）。

查錯時一定要再檢查幾遍數(shù)組范圍。

這么裸的最短路不用再解釋了吧。把第m條邊的權(quán)值設(shè)為0，先跑一次最短路，屏蔽掉地m條邊跑出次長路的值，最后針對每一次最后一條邊的權(quán)值判斷要輸出誰就可以了。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<queue> 6 #include<algorithm> 7 8 #define For(i,a,b) for(register int i=a;i<=b;++i) 9 #define Re register 10 #define llg long long 11 #define inf 0x7f7f7f 12 #define Pn putchar('\n') 13 using namespace std; 14 const int N=2e5+10,M=5e5+10; 15 int head[N],nxt[M*2],v[M*2],cnt=0; 16 int n,m,k,x,y; 17 llg w[M*2],Dis,cDis,z; //就是在這個地方的M寫成N了，爆掉了一半的分?jǐn)?shù)。 18 inline void read(int &v){ 19 v=0; 20 char c=getchar(); 21 while(c<'0'||c>'9')c=getchar(); 22 while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar(); 23 } 24 inline void read(llg &v){ 25 v=0; 26 char c=getchar(); 27 while(c<'0'||c>'9')c=getchar(); 28 while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar(); 29 } 30 void write(llg x){ 31 if(x>9)write(x/10); 32 int xx=x%10; 33 putchar(xx+'0'); 34 } 35 void add(int ux,int vx,llg wx){ 36 cnt++; 37 nxt[cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx; w[cnt]=wx; 38 cnt++; 39 nxt[cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux; w[cnt]=wx; 40 } 41 42 struct Qr{ 43 llg x; 44 int id; 45 bool operator<(const Qr &a)const{ 46 return a.x<x; 47 } 48 }; 49 priority_queue<Qr>q; 50 51 llg d[N],nf; 52 void Djs(int chs){ 53 memset(d,inf,sizeof(d)); 54 nf=d[0]; 55 d[1]=0; q.push( (Qr) {0,1} ); 56 while(!q.empty()){ 57 Qr tp=q.top(); q.pop(); 58 if(d[tp.id]<tp.x)continue; 59 for(Re int i=head[tp.id];i;i=nxt[i]){ 60 if(chs&&w[i]==0)continue; 61 int vv=v[i]; 62 if(tp.x+w[i]<d[vv]){ 63 d[vv]=tp.x+w[i]; 64 q.push((Qr){d[vv],vv}); 65 } 66 } 67 } 68 } 69 70 int main(){ 71 // freopen("monogatari.in","r",stdin); 72 // freopen("monogatari.out","w",stdout); 73 read(n); read(m); read(k); 74 For(i,1,m-1){ 75 read(x); read(y);read(z); 76 add(x,y,z); 77 } 78 read(x); read(y); add(x,y,0); 79 Djs(0); Dis=d[n]; 80 Djs(1); cDis=d[n]; 81 82 For(i,1,k){ 83 read(x); 84 if(Dis>=nf){ //這個地方的>=忘記寫=號了。。 85 printf("+Inf\n"); 86 continue; 87 } 88 if(Dis+x<cDis){ 89 write(Dis+x); Pn; 90 }else{ 91 write(cDis); Pn; 92 } 93 } 94 fclose(stdin); fclose(stdout); 95 return 0; 96 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/HLAUV/p/9876864.html

總結(jié)

以上是生活随笔為你收集整理的物语（最短路）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。