多起点多终点

以图为例

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;

struct node{    
    int total;  
    int id;     
}num[30];
int graph[30][30];
String  res[30]={"S1","S2","S3","S4","S5","A1","A2","A3","A4","A5","B1","B2","B3","B4","B5","C1","C2","C3","C4","C5","T1","T2","T3","T4","T5"};
int main(){
    int vst,ved,val;
    for(int i=0;i<32;i++){
         cin>>vst>>ved>>val;
         graph[vst][ved]=val;     
    }   
    int maxn=20,minn=16;    
    for(int i=4;i>=1;--i){  
        int tmp;    
        if(i%2==0)  tmp=5;  
        else   tmp=4;
        for(int j=maxn;j>=minn;--j){    
            if(graph[j][j+tmp]&&graph[j][j+tmp+1]){ 
                 if(graph[j][j+tmp]+num[j+tmp].total>graph[j][j+tmp+1]+num[j+tmp+1].total){  
                     num[j].total+=graph[j][j+tmp+1]+ num[j+tmp+1].total;
                     num[j].id=j+tmp+1;
                }       
                else{
                    num[j].total+=graph[j][j+tmp]+num[j+tmp].total;
                     num[j].id=j+tmp;
                }
            }
            else if(graph[j][j+tmp]&&!graph[j][j+tmp+1]){                    
                num[j].total+=graph[j][j+tmp]+num[j+tmp].total;
                num[j].id=j+tmp;
            }
            else if(!graph[j][j+tmp]&&graph[j][j+tmp+1]){
                 num[j].total+=graph[j][j+tmp+1]+num[j+tmp+1].total;
                 num[j].id=j+tmp+1;
            }
        }
        maxn-=5;
        minn-=5;
    }
    int ans=10086;          
    for(int i=1;i<=5;i++){
        if(ans>num[i].total){
            ans=num[i].total;
            num[0].id=i;
        }
    }
    cout<<ans<<endl;
    for(int i=0;num[i].id!=0;i=num[i].id)
        cout<<res[num[i].id-1]<<" ";        
    cout<<endl;
    return 0;
}