核心结论：针对您描述的政府工程欠款问题，结合合同、决算、发票等完备手续，可通过以下途径解决，我将从法律程序、实务操作、风险防范三个角度为您详细分析。

一、法律程序：诉讼是核心救济途径

1. 诉讼主体与管辖
   根据《民法典》第807条及《政府采购法》相关规定，您作为承包方有权以发包方（政府相关部门）为被告提起民事诉讼。需注意：

   • 若合同明确约定仲裁条款，则需申请仲裁而非诉讼；
     
   • 管辖法院通常为工程所在地或被告住所地法院，建议优先选择工程所在地法院（便于调查取证）。

2. 证据链构建
   您已具备关键证据：

   • 合同：证明双方权利义务关系；
     
   • 决算文件：确认工程最终价款；
     
   • 发票：证明您已履行纳税义务且发包方未支付对应款项。
     补充建议：若存在催款记录（如微信、邮件、书面函件），需一并提交，以证明您持续主张权利。

3. 诉讼时效问题
   根据《民法典》第188条，诉讼时效为3年，自您知道或应当知道权利受损之日起计算。实务中：

   • 若您曾多次催款，时效从最后一次催款之日起重新计算；
     
   • 建议立即起诉，避免因领导更换导致对方以“超过时效”抗辩。

二、实务操作：非诉手段可同步推进

1. 行政投诉
   向上级财政部门或审计部门投诉，依据《政府投资条例》第29条，政府投资项目不得拖欠工程款。投诉时需提交：

   • 合同、决算、发票复印件；
     
   • 书面投诉信（明确诉求及事实依据）。
     优势：行政压力可能推动快速解决，尤其适用于财政资金未拨付到位的情况。

2. 申请支付令
   若证据充分且无争议，可依据《民事诉讼法》第221条向法院申请支付令。需满足：

   • 债权债务关系明确；
     
   • 支付令能够送达债务人。
     注意：若对方在15日内提出异议，支付令失效，需转为诉讼程序。

三、风险防范：避免后续纠纷升级

1. 财产保全申请
   起诉时同步申请财产保全，冻结发包方银行账户或等值财产（如房产、车辆）。需提供：

   • 保全申请书；
     
   • 担保（可通过保险公司出具保函，降低成本）。
     目的：防止对方转移资产，确保判决后能执行到位。

2. 领导更换不影响责任承担
   政府工程欠款属于单位债务，不因领导更换而免除。新任领导需继续履行合同义务，您可向现任负责人主张权利。

四、特殊情形处理

1. 财政资金未拨付
   若因财政紧张导致欠款，可要求发包方出具财政资金安排证明，并协商分期支付方案。若协商无果，仍需通过诉讼确认债权，待财政资金到位后优先受偿。

2. 工程存在质量问题抗辩
   若对方以工程质量为由拒付，需审查合同约定及决算文件。若决算已确认质量合格，对方抗辩不成立；若存在争议，可能需启动质量鉴定程序。

行动建议：

1. 立即整理所有证据材料（合同、决算、发票、催款记录）；
   
2. 委托律师起草《律师函》正式催款，固定证据并施加压力；
   
3. 若7日内未获回应，同步启动诉讼与行政投诉程序。
   

您的情况法律关系清晰，证据充分，通过法律途径解决的成功率较高。如有进一步疑问或需协助起草文书，可直接向我咨询。