生活随笔
收集整理的這篇文章主要介紹了
week7 TT的旅行日记
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Title
Input
Output
樣例
input
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
output
1 2 4
2
5
分析
- 給定起點(diǎn)S和終點(diǎn)S，分別求出起點(diǎn)和終點(diǎn)到各個(gè)點(diǎn)的花費(fèi)，存儲(chǔ)在disS和disE。
- 枚舉每一條商業(yè)線(xiàn)（u,v,w），則如果使用這條商業(yè)線(xiàn)，最小花費(fèi)為min(disS[u]+dis[v]+w, disE[u]+disS[v]+w)。找出使用一條商業(yè)線(xiàn)的最小花費(fèi)。
- 使用商業(yè)線(xiàn)的最小花費(fèi)與不使用商業(yè)線(xiàn)的最小花費(fèi)作比較，誰(shuí)小取誰(shuí)。
- 在求取起點(diǎn)和終點(diǎn)到各個(gè)距離的花費(fèi)，使用的是dijkstra。
- 有可能必須需要一條商業(yè)線(xiàn)才能到達(dá)，這種情況下，不添加商業(yè)線(xiàn)時(shí)，起點(diǎn)和終點(diǎn)不連通 ,互不相通的點(diǎn)花費(fèi)為無(wú)窮，枚舉商業(yè)線(xiàn)的時(shí)候也能選到在加上商業(yè)線(xiàn)后最小的花費(fèi)。
總結(jié)
寫(xiě)代碼的時(shí)候，寫(xiě)的是while(scanf())導(dǎo)致一直runtime error，/(ㄒoㄒ)/~~。
注意在枚舉商業(yè)線(xiàn)（u，v，w）時(shí)，如果判斷得到的最小花費(fèi)是disS[u]+dis[v]+w，則該商業(yè)線(xiàn)記為（u，v）。若選用的是disE[u]+disS[v]+w，則記錄的為（v，u），因?yàn)槭菑慕K點(diǎn)方向來(lái)的。
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std
;
#define rangeEdge 2000+10
#define maxW 100000000
#define range 500+10
struct qNode
{int first
;int second
;qNode(int f
= 0, int s
= 0){first
= f
;second
= s
;}bool operator<(const qNode
& b
)const{return first
> b
.first
;}
};
struct Edge
{int v
, w
, nxt
;Edge(int tv
, int tw
, int tnxt
){v
= tv
; w
= tw
; nxt
= tnxt
;}Edge(){v
= 0; w
= 0; nxt
= 0;}
};
int ecoNum
= 0, N
= 0, S
= 0, E
= 0, M
= 0, K
= 0, flag
= 0;
int ecohead
[range
], vis
[range
], disS
[range
], disE
[range
], preS
[range
], preE
[range
];
Edge eco
[rangeEdge
];
void addeco(int tu
, int tv
, int tw
)
{eco
[ecoNum
].v
= tv
; eco
[ecoNum
].w
= tw
; eco
[ecoNum
].nxt
= ecohead
[tu
];ecohead
[tu
] = ecoNum
;ecoNum
++;
}
void dijkstra(int s
, int* dis
, int* pre
)
{priority_queue
<qNode
> q
;for (int i
= 0; i
< range
; i
++){dis
[i
] = maxW
;vis
[i
] = 0;pre
[i
] = 0;}dis
[s
] = 0;pre
[s
] = -1;q
.push(qNode(0, s
));while (!q
.empty()){int now
= q
.top().second
;q
.pop();if (vis
[now
]) continue;vis
[now
] = 1;for (int i
= ecohead
[now
]; i
!= -1; i
= eco
[i
].nxt
){int next
= eco
[i
].v
, w
= eco
[i
].w
;if (dis
[next
] > dis
[now
] + w
){dis
[next
] = dis
[now
] + w
;pre
[next
] = now
;q
.push(qNode(dis
[next
], next
));}}}
}void outputS(int x
)
{if (x
== S
){printf("%d", x
);return;}outputS(preS
[x
]);printf(" %d", x
);
}
void outputE(int x
)
{while (x
!= E
){printf(" %d", x
);x
= preE
[x
];}printf(" %d", x
);
}
int main()
{while (scanf("%d %d %d", &N
, &S
, &E
)!=EOF){ecoNum
= 0;int tempu
= 0, tempv
= 0, tempw
= 0;memset(ecohead
, -1, sizeof(ecohead
));scanf("%d", &M
);while (M
--){scanf("%d %d %d", &tempu
, &tempv
, &tempw
);addeco(tempu
, tempv
, tempw
);addeco(tempv
, tempu
, tempw
);}dijkstra(S
, disS
, preS
);dijkstra(E
, disE
, preE
);scanf("%d", &K
);int busa
= -1, busb
= -1, mindis
= disS
[E
];while (K
--){int u
= 0, v
= 0, w
= 0;scanf("%d %d %d", &u
, &v
, &w
);int d1
= disS
[u
] + disE
[v
] + w
;int d2
= disE
[u
] + disS
[v
] + w
;if (mindis
> d1
){mindis
= d1
;busa
= u
; busb
= v
;}if (mindis
> d2
){mindis
= d2
;busa
= v
; busb
= u
;}}if (flag
> 0) printf("\n");if (busa
== -1){outputS(E
);printf("\nTicket Not Used\n");printf("%d\n", mindis
);}else{outputS(busa
);outputE(busb
);printf("\n%d\n%d\n", busa
, mindis
);}flag
++;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的week7 TT的旅行日记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
