1018 Public Bike Management（单源最短+DFS搜索）

分析：求最短路径。如果最短路径有多个，求能带的最少的自行车数目的那条。如果还是有很多条不同的路，那么就找一个从车站带回的自行车数目最少的

调成了21/30.
还在看哪里写错了，这题写了快1天了,orz。。。
打算换一种方法，在最短路径后，直接dfs，把所有满足最短路情况的路径都存在vecoctor中，然后继续一个sort排序，输出第一个即可。
可以参考这个作者的博客：https://www.cnblogs.com/weedboy/p/7256552.html

得分：21/30

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 510
using namespace std;
int mp[maxn][maxn],vis[maxn],lowcost[maxn];
int bike[maxn],visit[maxn];
int path[maxn],pre[maxn];
int cmax,n,sp,m,ans,maxBike;
int minNeed=-inf,minBack=inf;
vector<int> tp,pp;
int dijkstra(int s,int e){
    for(int i=0;i<=n;i++){
    lowcost[i]=mp[s][i];}vis[s]=1;lowcost[s]=0;for(int i=0;i<=n;i++){
    int minn=inf;int v=-1;for(int j=0;j<=n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<=n;j++){
    if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
    lowcost[j]=lowcost[v]+mp[v][j];}}}return lowcost[e];
}
void dfs(int x,int dis,int need,int backk){
    visit[x]=1;//cout<<"dis= "<<dis<<endl;if(dis>ans){
    return ;}if(x==sp &&dis==ans){
    //cout<<need<<" "<<minNeed<<endl;if(need>minNeed){
    minNeed=need;minBack=backk;pp=tp;}else if(need==minNeed&&backk<minBack){
    minBack=backk;pp=tp;}// cout<<"minNeed= "<<minNeed<<endl;return ;}for(int i=1;i<=n;i++){
    if(!visit[i]&&mp[x][i]!=inf){
    // cout<<"i= "<<i<<endl;visit[i]=1;tp.push_back(i);if(bike[i]>0){
    dfs(i,dis+mp[x][i],need,backk+bike[i]);}else{
    if(bike[i]<0&&backk>(-1*bike[i])){
    dfs(i,dis+mp[x][i],need,backk+bike[i]);}else{
    dfs(i,dis+mp[x][i],need+(backk+bike[i]),0);}}visit[i]=0;tp.pop_back();}}return ;
}int main(){
    for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    mp[i][j]=inf;}mp[i][i]=0;}cin>>cmax>>n>>sp>>m;for(int i=1;i<=n;i++){
    cin>>bike[i];bike[i]-=cmax/2;}for(int i=0;i<m;i++){
    int x,y,z;cin>>x>>y>>z;if(mp[x][y]>z){
    mp[x][y]=mp[y][x]=z;}}ans=dijkstra(0,sp);dfs(0,0,0,0);int tmpp=-1*minNeed;if(tmpp<0){
    cout<<"0 0";}else{
    cout<<-1*minNeed<<" 0";}for(int i=pp.size()-2;i>=0;i--){
    cout<<"->"<<pp[i];}cout<<"->"<<sp;cout<<" "<<minBack<<endl;return 0;
}

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 510
using namespace std;
int mp[maxn][maxn],vis[maxn],lowcost[maxn];
int bike[maxn],visit[maxn];
int path[maxn],pre[maxn];
int cmax,n,sp,m,ans,maxBike;
int dijkstra(int s,int e){
    for(int i=0;i<=n;i++){
    lowcost[i]=mp[s][i];}vis[s]=1;lowcost[s]=0;for(int i=0;i<=n;i++){
    int minn=inf;int v=-1;for(int j=0;j<=n;j++){
    if(!vis[j]&&lowcost[j]<minn){
    minn=lowcost[j];v=j;}}if(v==-1) break;vis[v]=1;for(int j=0;j<=n;j++){
    if(!vis[j]&&lowcost[v]+mp[v][j]<lowcost[j]){
    lowcost[j]=lowcost[v]+mp[v][j];}}}return lowcost[e];
}
void dfs(int x,int dis,int bikeNum){
    visit[x]=1;if(dis>ans){
    return ;}if(x==sp &&dis==ans){
    if(bikeNum>maxBike){
    //cout<<"bikeNum= "<<bikeNum<<endl;maxBike=bikeNum;memcpy(path,pre,sizeof(pre));}return ;}for(int i=1;i<=n;i++){
    if(!visit[i]&&mp[x][i]!=inf){
    pre[i]=x;visit[i]=1;dfs(i,dis+mp[x][i],bikeNum+bike[i]-cmax/2);visit[i]=0;}}
}int main(){
    for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    mp[i][j]=inf;}mp[i][i]=0;}cin>>cmax>>n>>sp>>m;for(int i=1;i<=n;i++){
    cin>>bike[i];}for(int i=0;i<m;i++){
    int x,y,z;cin>>x>>y>>z;if(mp[x][y]>z){
    mp[x][y]=mp[y][x]=z;}}ans=dijkstra(0,sp);maxBike=-inf;dfs(0,0,0);int b[maxn];int curr=0;b[curr++]=sp;while(1){
    b[curr++]=path[sp];if(path[sp]==0) {
    path[curr]=0;break;}sp=path[sp];}cout<<curr<<" ";for(int i=curr-1;i>=0;i--){
    cout<<b[i];if(i!=0) {
    cout<<"->";}else {
    cout<<" ";}}if(maxBike<=0) {
    cout<<"0"<<endl;}else{
    cout<<maxBike<<endl;}return 0;
}